POJ 3259 Wormholes：Bellman-Ford 檢測負權環

問題描述

星球間有雙向道路（正權）與單向蟲洞（負權）。判斷是否存在負權環（即可時間旅行）。多測資，輸出 YES/NO。

解法：Bellman-Ford 判負環

• 道路雙向：加兩條正權邊。
• 蟲洞單向：加一條負權邊（權重 = -w）。
• 超級源點連接所有節點權重 0，或直接初始化所有點距離為 0，跑 V 輪鬆弛，第 V 輪仍能鬆弛 → 存在負環。

核心代碼

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int SIZE = 11111;
const int MAXLEN = 1<<30;
struct Edge { int s, e, v; } ed[SIZE];
int N, M, WH, dis[SIZE], ednum;

bool Bellman() {
    for (int i = 0; i < N-1; i++) {
        bool flag = false;
        for (int j = 0; j < ednum; j++) {
            if (dis[ed[j].e] > dis[ed[j].s] + ed[j].v) {
                flag = true;
                dis[ed[j].e] = dis[ed[j].s] + ed[j].v;
            }
        }
        if (!flag) break;
    }
    for (int j = 0; j < ednum; j++)
        if (dis[ed[j].e] > dis[ed[j].s] + ed[j].v)
            return true;
    return false;
}

int main() {
    int f, u, v, w;
    cin >> f;
    while (f--) {
        ednum = 0;
        cin >> N >> M >> WH;
        for (int i = 0; i < M; i++) {
            cin >> u >> v >> w;
            ed[ednum++] = {u, v, w};
            ed[ednum++] = {v, u, w};
        }
        for (int i = 0; i < WH; i++) {
            cin >> u >> v >> w;
            ed[ednum++] = {u, v, -w};
        }
        if (Bellman()) printf("YES\n"); else printf("NO\n");
    }
    return 0;
}

關鍵點

1. 初始化 `dis` 為 0 等價於加入超級源點，簡化代碼。
2. 提前終止：某輪無鬆弛直接跳出，優化效能。
3. 邊數雙向道路計兩條，蟲洞一條，總邊數 ≤ 2M+W。

複雜度

O(V·E)，V≤500，E≤2500，極快。