/*求解单源最短路问题：Bellman-Ford算法（可判负权回路）注：负权回路： 如果存在一个回路（首尾相同的路径），而且这个回路上所有权值之和是负数，那这就是一个负权回路。 f[i] := 从起点s出发到节点i的最短距离故： f[i] = min(f[j] + dis[i][j]) 初始值： f[] = INF f[s] = 0; 自己当时遇到的疑惑，以及参考了相关资料获得的解答：（1）在实现时，最外侧循环的迭代次数为什么最大是|V|-1次？（|V|节点的个数） 答： 前提：在图中不存在负权回路 一共有n个节点，求1->n的最短距离，我们知道1->n的最短路径，最多有(n-1)条边。 （如果大于(n-1)，说明有一个节点在最短路径上走了两次，即走了一个圈， 若圈的权为正：显然包含整个圈的路径必定不是最短路径； 若圈的权为负：最短路径不存在，因为到达节点的路径距离可以无限变小； 若圈的权为0： 去掉之后不影响最优解。 ） 在每次循环中，我们利用f[i] = min(f[j] + dis[i][j])来更新(s->i)的边，每 次循环必定会更新成功一条边（更新成功指的是：这条边的权值也是最终最短路径的权值）， 那么需要(n-1)次循环才可以更新掉所有的边。 在《数据结构与编程实验--大学生程序设计课程与竞赛训练教材》（）上， 有说到： 很多时候，需要的迭代次数远小于|V|-1，所以可以考虑在每次循环中设置的update的标记， 如果没有update，则说明已获得最优解，跳出循环即可。 时间复杂度：O(V*E) （2）为什么如果f[i]>f[j]+dis[j][i]，可以判定有负权回路？ 答： 根本原因：求解最短路时 f[i] = min(f[j] + dis[i][j]) 在|V|-1此循环结束，即已获得最优解，如果在图中不存在负权回路，那么必然是f[i]<=f[j]+dis[j][i]， 否则必然存在s->i的路径距离比f[i]更短，与已获得最优解矛盾。 代码： for (int i = 0; i < eg.size(); ++i) { if (f[eg[i].egto] > f[eg[i].egfrom] + eg[i].egfrom) { return false; // 出现负权回路 } return true; // 没有出现负权回路 } eg: 初始： 边更新后： 3 > 0 + 2 => 出现负权回路 -------------------------------------------------------poj 3268 Silver Cow Party what is the longest amount of time a cow must spend walking to the party and back？故此题需要解决两个问题： （1）所有节点到达节点X的最短距离； 对于此问题，可以反过来想：从X节点到达所有节点的最短距离，答案不变。 但是此时初始存储的有向边的方向需要调换 （原因：路是单向的，a->b反过来想a<-b，边的方向发生了改变， 边的权值不变，求解a->b的最短路也就是求a<-b的最短路 ） （2）节点X到达所有节点的最短距离。 按初始存储的有向边进行计算 答案： max{ walkTo[i]+returnTo[i] } */ 1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include