UVA558

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;
}