UVA558 - Wormholes（BellmanFord判负环）

UVA558 - Wormholes

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

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

代码：

#include 
   
     #include 
    
      #include 
     
       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"); else printf ("not possible\n"); } return 0; }