狄杰斯特拉算法模板--最短路径

#include<cstdio> #include<iostream> #include<algorithm> #include<vector> const int maxn=1000; const int inf=0x3fffffff; using namespace std; int n,m,index,G[maxn][maxn],dis[maxn]; bool vis[maxn]={false}; void digkstra(int s) { fill(dis,dis+maxn,inf); dis[s]=0; for(int i=0;i<n;i++) { int min=inf,u=-1; for(int j=0;j<n;j++) { if(vis[j]==false&&dis[j]<min) { min=dis[j]; u=j; } } if(u==-1)return; vis[u]=true; for(int v=0;v<n;v++) { if(vis[v]==false&&G[u][v]!=inf&&dis[u]+G[u][v]<dis[v]) { dis[v]=dis[u]+G[u][v]; } } } } int main() { cin>>n>>m>>index; int a,b,d; fill(G[0],G[0]+maxn*maxn,inf); for(int i=0;i<m;i++) { scanf("%d %d %d",&a,&b,&d); G[a][b]=d; } digkstra(index); for(int i=0;i<n;i++) { printf("%d\n",dis[i]); } }