POJ 3259 Wormholes：Bellman-Ford 判斷負環（鄰接矩陣版）

問題描述

N 個星系，M 條雙向道路（正權），W 條單向蟲洞（負權）。判斷是否存在**負權環**（可時間旅行）。

Bellman-Ford 核心思想

對所有邊進行 N 輪松弛。若第 N 輪仍有更新 → 存在負環。
時間 O(N·E)，N≤500, E≤2M+W≤5000 可接受。

鄰接矩陣實現

const int INF = 0x3f3f3f3f;
int G[505][505]; // 鄰接矩陣
int dist[505];

bool bellmanFord(int n) {
    fill(dist, dist+n+1, 0); // 超級源點連向所有點權 0
    for (int i=1;i<=n;++i) {
        bool updated = false;
        for (int u=1;u<=n;++u)
            for (int v=1;v<=n;++v)
                if (G[u][v] < INF && dist[v] > dist[u] + G[u][v]) {
                    dist[v] = dist[u] + G[u][v];
                    updated = true;
                    if (i==n) return true; // 第 N 輪更新 → 負環
                }
        if (!updated) break; // 提前終止
    }
    return false;
}

圖構建細節

• 初始化 G[u][v] = INF。
• 道路：G[u][v] = G[v][u] = min(G[u][v], w)（保留最小權）。
• 蟲洞：G[u][v] = min(G[u][v], -w)（單向負權）。
• 添加超級源點 0 → 所有點權 0，或直接初始化 dist[i]=0 等價。

SPFA 判負環（更快）

SPFA 計數入隊次數，若某點入隊 ≥ N 次 → 負環。代碼見 3921。鄰接表版本更節省內存且實際更快。

複雜度對比