bellman

codelyt

在bellman中模板一般都是这个样子

1. for(int k=1;k<=n-1;k++)
   
2. {
   
3.     flag=0;
   
4.     for(int j=1;j<=m;j++)
   
5.     {
   
6.         if(dis[v[j]]>dis[u[j]]+w[j])
   
7.         {
   
8.             dis[v[j]]=dis[u[j]]+w[j];
   
9.             flag=1;
   
10.         }
    
11.     }
    
12.     if(flag==0)
    
13.     {
    
14.           break;
    
15.       }
    
16.   }

复制代码

但试一试这组测试数据：

1. 6 5
   
2. 2 4 -10
   
3. 4 6 -10
   
4. 2 5 -10
   
5. 5 6 -10
   
6. 3 6 -10

复制代码

结果输出了，但我们发现这个图根本不连通！ 所以最短路算法（搜索除外）都应该判断1号点到u号点连不连通。