1 #include <bits/stdc++.h> 2 const int INF=99999; 3 using namespace std; 4 5 int main() 6 { 7 int dis[105] , i , k , n , m , u[105] , v[105] , w[105]; 8 bool flag=false; 9 cin>>n>>m; 10 for(int i=1;i<=m;i++) 11 { 12 cin>>u[i]>>v[i]>>w[i]; //分别为i点 j点 i到j 的距离 13 } 14 for(i = 1;i <= n;i++) 15 dis[i] = INF; 16 dis[1]=0; 17 for(int k=1;k<=n;k++) //k次循环,松弛k次 18 { 19 for(int i=1;i<=m;i++) 20 { 21 if(dis[v[i]]>dis[u[i]]+w[i]) 22 dis[v[i]]=dis[u[i]]+w[i]; 23 } 24 } 25 for(int i=1;i<=m;i++) //此处的感觉有点类似找环的意思 26 { 27 if(dis[v[i]]>dis[u[i]]+w[i]) 28 flag=true; 29 } 30 if(!flag) 31 { 32 for(int i=1;i<=n;i++) 33 { 34 cout<<dis[i]<<' '; 35 } 36 } 37 else 38 { 39 cout<<"存在负环"<<endl; 40 } 41 42 }