POJ 2387：Bellman-Ford 判斷負環（蟲洞時間旅行）

問題描述

N 個星球，M 條雙向路（耗時正），W 個單向蟲洞（耗時負，可回溯時間）。問是否存在從某星球出發經路徑回到原點且總耗時 < 0（即負環）。

Bellman-Ford 算法

對每個起點跑 Bellman-Ford（或加超級源點連向所有點權 0 跑一次）。若第 N 輪鬆弛仍有更新，則存在負環。

關鍵細節

• 路是雙向的，蟲洞是單向的。建圖時路加兩條邊，蟲洞加一條負權邊。
• N ≤ 500, M ≤ 2500, W ≤ 200，邊數 ≤ 5200，BF O(N·E) ≈ 2.6×10⁶ 可行。
• 需對每個連通分量檢查，或加超級源點 0 向所有點連 0 權邊，跑一次 BF 即可。

代碼實現

#include 
#include 
const int INF = 0x3f3f3f3f;
struct Edge { int u, v, w; };
Edge es[5500];
int d[505];

bool bellman_ford(int n, int m) {
    memset(d, 0x3f, sizeof(d));
    d[1] = 0; // 或超級源點 0
    for (int i = 1; i <= n; ++i) {
        bool relaxed = false;
        for (int j = 0; j < m; ++j) {
            if (d[es[j].u] != INF && d[es[j].u] + es[j].w < d[es[j].v]) {
                d[es[j].v] = d[es[j].u] + es[j].w;
                relaxed = true;
                if (i == n) return true; // 第 n 輪仍能鬆弛 → 負環
            }
        }
        if (!relaxed) break;
    }
    return false;
}

int main() {
    int F; scanf("%d", &F);
    while (F--) {
        int N, M, W; scanf("%d%d%d", &N, &M, &W);
        int cnt = 0;
        for (int i=0, u,v,w; i