UVA 558 Wormholes：Bellman-Ford 判斷負環

題目大意

有 N 個星系 (節點)，M 個蟲洞 (有向邊)，每條邊有權重 (時間)。教授想利用蟲洞回到過去，即尋找是否存在負權環 (總權重 < 0 的環)。輸出 "possible" 或 "not possible"。

Bellman-Ford 核心原理

• 單源最短路徑鬆弛 N-1 輪後，若第 N 輪仍能鬆弛，則存在負環。
• 本題不指定起點，需檢測圖中任意位置是否有負環。技巧：加入超級源點 0，向所有節點連邊權 0，從 0 跑 Bellman-Ford。

完整程式碼 (C++)

#include 
using namespace std;

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int N, M; cin >> N >> M;
        vector edges;
        edges.reserve(M + N);
        for (int i=0;i>u>>v>>w;
            edges.push_back({u, v, w});
        }
        // 超級源點 0 -> 所有節點 (1~N)，權重 0
        for (int i=1;i<=N;++i) edges.push_back({0, i, 0});

        vector dist(N+1, INF);
        dist[0] = 0;
        bool hasNegCycle = false;

        // N 輪鬆弛 (含超級源點共 N+1 個節點，需 N 輪)
        for (int i=0;i dist[e.u] + e.w) {
                    dist[e.v] = dist[e.u] + e.w;
                    updated = true;
                    if (i == N-1) hasNegCycle = true; // 第 N 輪仍更新
                }
            }
            if (!updated) break; // 提前收斂
        }
        cout << (hasNegCycle ? "possible" : "not possible") << '\n';
    }
    return 0;
}

關鍵細節

1. 超級源點：確保圖中所有連通分量都被掃描到，否則離散的負環會被漏檢。
2. 節點編號：題目節點 0~N-1 或 1~N，代碼統一處理。
3. 提前終止：若某輪無更新，後續輪也不會更新，直接跳出。
4. 長整型：權重累加可能超 int，建議用 long long。

複雜度

• 時間：O(T · N · (M+N))，N ≤ 1000, M ≤ 2000 極快。
• 空間：O(M+N)。

延伸：SPFA 優化

隊列優化 Bellman-Ford (SPFA) 平均更快，但最壞仍 O(NM) 且有 Hack 數據導致 TLE。競程建議用標準 Bellman-Ford 或 SLF/LLL 優化版 SPFA。