UVA558 - Wormholes（BellmanFord判负环）

UVA558 - Wormholes（BellmanFord判负环）

UVA558 - Wormholes

题目大意： 
有一个教授希望利用虫洞回到过去(还是从这个虫洞出来就到达了过去），给你虫洞形成的有向图，问教授能否回到过去。

解题思路: 
利用BellmanFord判负环，如果不存在负环的话，那么最多经过N - 1次迭代就可以得到最短路，因为形成最短路最多N - 1个节点（起点不算），但是如果存在了负环，那么就可以一直迭代，最短路会越来越小。可以利用这个性质来判断是否存在负环。

代码：

#include <cstdio>
#include <cstring>
#include <queue>const int maxn = 1005;
const int maxm = 2005;using namespace std;struct edge {int u, v;int d;
}e[maxm];const int INF = 0x7f7f7f7f;
int N, M;
int d[maxn];bool BellmanFord() {for (int i = 0; i < N; i++)d[i] = i == 0 ? 0 : INF;d[0] = 0;for (int k = 0; k < N - 1; k++) for (int i = 0; i < M; i++) {if (d[e[i].u] != INF && d[e[i].v] > d[e[i].u] + e[i].d)d[e[i].v] = d[e[i].u] + e[i].d;}for (int i = 0; i < M; i++)if (d[e[i].u] != INF && d[e[i].v] > d[e[i].u] + e[i].d) return true;return false;
}int main () {int T;scanf ("%d", &T);while (T--) {scanf ("%d%d", &N, &M);for (int i = 0; i < M; i++)scanf ("%d%d%d", &e[i].u, &e[i].v, &e[i].d);if (BellmanFord()) printf ("possible\n");elseprintf ("not possible\n");}return 0;
}