1 #include <bits/stdc++.h> 2 const int INF=99999; 3 using namespace std; 4 int n,m,u; 5 int dis[10000]; 6 int dist[10000][10000]; 7 int vis[10000]; 8 int main() 9 { 10 cin>>n>>m; 11 int a,b,c; 12 for(int i=1;i<=n;i++) 13 { 14 for(int j=1;j<=n;j++) 15 { 16 if(i==j) dist[i][j]=0; 17 else 18 { 19 dist[i][j]=INF; 20 } 21 } 22 } 23 memset(vis,0,sizeof(vis)); 24 vis[1]=1; 25 26 27 for(int j=1;j<=m;j++) 28 { 29 cin>>a>>b>>c; 30 dist[a][b]=c; 31 } 32 33 for(int i=1;i<=n;i++) 34 { 35 dis[i]=dist[1][i]; 36 } 37 for(int i=1;i<=n-1;i++) //类似于找相近的点相连 38 { 39 int minn=INF; 40 for(int j=1;j<=n;j++) 41 { 42 if(vis[j]==0&&dis[j]<minn) 43 { 44 minn=dis[j]; 45 u=j; 46 } 47 } 48 vis[u]=1; 49 for(int v=1;v<=n;v++) //此处判断两条路那一条更近一点 松弛 50 { 51 if(dist[u][v] < INF) 52 { 53 if(dis[v] > dis[u] + dist[u][v]) 54 dis[v] = dis[u] + dist[u][v]; 55 } 56 57 } 58 } 59 for(int i=1;i<=n;i++) 60 { 61 cout<<dis[i]<<' '; 62 } 63 }