1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            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 }