1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 #include <queue> 7 #define inf 0x3f3f3f3f 8 const int maxn = 200; 9 int n, m, pre[maxn], edge[maxn * maxn][3]; 10 int dist[maxn]; 11 bool relax(int u, int v, int c){ 12 if(dist[v] > dist[u] + c){ 13 dist[v] = dist[u] + c; pre[v] = u; 14 return true; 15 } 16 return false; 17 } 18 int bellman(int S){ 19 int i, j; 20 for(i = 0; i < n; i ++){ 21 dist[i] = inf; 22 pre[i] = -1; 23 } 24 dist[S] = 0; 25 bool flag; 26 for(i = 1;i < n; i ++){ 27 flag = false; 28 for(j = 0; j < m; j ++) 29 if(relax(edge[j][0], edge[j][1], edge[j][2])) flag = true; 30 if(!flag) break; 31 } 32 for(j = 0; j < m; j ++) 33 if(relax(edge[j][0], edge[j][1], edge[j][2])) return false; 34 return true; 35 }