POJ3259 Wormholes（最短路径）

题意;

有n个农场，m条双向路，之中有w个虫洞，虫洞为单向路，从起点到终点耗时反而是负数，求能否追上自己也就是判断是否有负权回路。

要点：

负权回路就是回路的权值之和为负数的意思，只要出现负权回路了，无论什么算法都是求不出最短路径的。这里学习了一下bellman-ford算法，dijkstra算法虽然很好写，但是是无法处理有负权的最短路径的，而bellman-ford算法可以算出有负权的最短路径，并且可以判断有无负权回路。

描述性证明：
　　首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
　　其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。
　　在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。
　　每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，所以有了SPFA算法）
　　如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。
　　如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。

参考来源：点击打开链接

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0x3f3f3f3f
int n, m, w,num;
int dis[505];
struct edge
{int u, v, len;
}e[5500];bool bellman()
{memset(dis, INF, sizeof(dis));for (int i = 1; i <= n - 1; i++)//注意这里只要进行N-1次操作即可{bool flag = false;for (int j = 0; j < num; j++)if (dis[e[j].v]>dis[e[j].u] + e[j].len){dis[e[j].v] = dis[e[j].u] + e[j].len;flag = true;}if (!flag)		//如果一条边都没有松弛，说明已经找到最短路径，可以直接返回break;}for (int i = 0; i < num; i++)		if (dis[e[i].v]>dis[e[i].u] + e[i].len)//如果进行了N-1次操作后还能松弛，说明有负权回路return true;return false;
}int main()
{int t;scanf("%d", &t);while (t--){num = 0;int u, v, len;scanf("%d%d%d", &n, &m, &w);while (m--){scanf("%d%d%d", &u, &v, &len);e[num].u = u; e[num].v = v;e[num++].len = len;e[num].u = v; e[num].v = u;e[num++].len = len;}while (w--){scanf("%d%d%d", &u, &v, &len);e[num].u = u; e[num].v = v;e[num++].len = -len;}if (bellman())printf("YES\n");elseprintf("NO\n");}return 0;
}