POJ 3259 Wormholes：Bellman-Ford 算法檢測負環

題目大意

給定 N 個星球、M 條雙向道路、W 個單向蟲洞。道路花費時間為正，蟲洞花費時間為負（時間旅行）。判斷是否能從某個星球出發，經過一系列路徑回到起點，且總時間為負（即存在負環）。

解法：Bellman-Ford 檢測負環

將所有邊加入圖中：

• 雙向道路：添加兩條有向邊，權值為正
• 單向蟲洞：添加一條有向邊，權值為負

對圖運行 Bellman-Ford，若第 N 輪鬆弛仍能更新距離，則存在負環。

完整代碼實現

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
struct Edge {
    int u, v, w;
};

bool bellman_ford(int n, const vector<Edge>& edges) {
    vector<int> dist(n + 1, 0);  // 初始為 0 即可，因為只需檢測負環
    
    // 執行 n 輪鬆弛
    for (int i = 1; i <= n; i++) {
        bool updated = false;
        for (const auto& e : edges) {
            if (dist[e.v] > dist[e.u] + e.w) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
                // 第 n 輪仍能更新，說明有負環
                if (i == n) return true;
            }
        }
        if (!updated) break;  // 提前終止
    }
    return false;
}

int main() {
    int F;
    scanf("%d", &F);
    while (F--) {
        int N, M, W;
        scanf("%d%d%d", &N, &M, &W);
        vector<Edge> edges;
        
        for (int i = 0; i < M; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            edges.push_back({u, v, w});
            edges.push_back({v, u, w});  // 雙向
        }
        for (int i = 0; i < W; i++) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            edges.push_back({u, v, -w});  // 蟲洞權值為負
        }
        
        if (bellman_ford(N, edges))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

關鍵點

• 距離數組初始化為 0 而非 INF，因為圖可能不連通，需檢測所有連通分量
• 時間複雜度：O(N × (M+W))，N ≤ 500，M ≤ 2500，W ≤ 200 完全足夠
• SPFA 也可用於負環檢測，但最壞情況較慢