啊哈磊_编程从这里起步

标题: bellman的小问题 [打印本页]

作者: codelyt 时间: 2018-10-17 12:57
标题: bellman的小问题

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

for(int k=1;k<=n-1;k++){ flag=0; for(int j=1;j<=m;j++) { if(dis[v[j]]>dis[u[j]]+w[j]) { dis[v[j]]=dis[u[j]]+w[j]; flag=1; } } if(flag==0) { break; }}

但试一试这组测试数据：

6 52 4 -104 6 -102 5 -105 6 -103 6 -10

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

UOJ.png (96.53 KB, 下载次数: 15)

哈哈哈

欢迎光临啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)