1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 int i,j,n,m,g[1005][1005],dis[1005],x,y,z,vis[1005]; 8 int main() 9 { 10 cin>>n>>m; 11 for(int i=1;i<=n;i++) 12 for(int j=1;j<=n;j++) 13 g[i][j]=1000000000; //先初始化每一个最短路径一个特别大的数字 14 for(int i=1;i<=m;i++) 15 { 16 cin>>x>>y>>z; //x到y和他们的边权值z 17 g[x][y]=min(g[x][y],z);//更新他们的权值 18 } 19 for(int i=1;i<=n;i++) 20 dis[i]=1000000000; //初始化最短路径一个贼大的值 21 dis[1]=0; //这个点到自己的距离为0 22 for(int i=1;i<=n;i++) 23 vis[i]=0; //初始化访问点为0 24 for(int i=1;i<=n;i++) 25 { 26 int t=-1; //随随便便给t赋个值 27 for(int j=1;j<=n;j++) 28 { 29 if(vis[j]==0 && (t==-1 || dis[j]<dis[t])) //这个点没被访问过且要求的点直接到这个点的距离更小就报下来地址 30 t=j; 31 } 32 vis[t]=1; //把这个最小的点设置为已访问 33 for(int j=1;j<=n;j++) //此后就是把整个路分成两部分一部分是直接访问的一部分是后面间接访问的 34 { 35 if(vis[j]==0) //如果这个点没被访问过则可以进行搜索 36 dis[j]=min(dis[j],dis[t]+g[t][j]); //这个值更新上一个值加上某值到这个值的最小值 37 //松弛操作 38 } 39 } 40 for(int i=1;i<=n;i++) 41 printf("%d ",dis[i]); //输出每一个点到最初点的最小值 42 return 0; 43 }