POJ 3259 Wormholes SPFA 版：鄰接表 + 入隊計數判負環

SPFA 判負環原理

SPFA 是 Bellman-Ford 的佇列優化。維護 cnt[v] = 頂點 v 入隊次數。若 cnt[v] ≥ N，說明存在負環（最短路徑最多 N-1 條邊）。

鄰接表結構

struct Edge { int to, w, next; };
Edge edges[MAXE];
int head[MAXN], ecnt;

void addEdge(int u, int v, int w) {
    edges[ecnt] = {v, w, head[u]};
    head[u] = ecnt++;
}

SPFA 核心代碼

bool spfa(int n) {
    queue q;
    vector dist(n+1, 0), cnt(n+1, 0);
    vector inq(n+1, true); // 全點入隊（超級源點等價）
    for (int i=1;i<=n;++i) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u]=false;
        for (int e=head[u]; e!=-1; e=edges[e].next) {
            int v = edges[e].to, w = edges[e].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    q.push(v); inq[v]=true;
                    if (++cnt[v] >= n) return true; // 負環
                }
            }
        }
    }
    return false;
}

圖構建（同 3919）

• 道路：雙向 addEdge(u,v,w); addEdge(v,u,w);
• 蟲洞：單向 addEdge(u,v,-w);

優化技巧

• SLF (Small Label First)：新點距離 < 隊首距離 → 插隊首。
• LLL (Large Label Last)：隊首距離 > 平均距離 → 移隊尾。
• 這兩優化可大幅減少鬆弛次數，防止最壞情況退化。

複雜度

平均 O(E)，最壞 O(NE)。實際測試 POJ 3259 SPFA < 100ms，BF 矩陣版 ~1s。