UVa 10986 發送郵件：SPFA 求最短路徑完整解析

問題描述

給定 n 個 SMTP 伺服器（節點），m 條雙向光纜（邊），每條邊有延遲權重 w。求從伺服器 S 到 T 的最小總延遲。若不可達輸出 "unreachable"。多測試用例格式，節點數 < 20,000，邊數 < 50,000，權重 ≤ 10,000。

算法選擇：SPFA（隊列優化 Bellman-Ford）

雖然 Dijkstra + 堆優化 O(m log n) 理論更優，但 SPFA 在稀疏圖、權重非負且無負環情況下實際表現極佳，代碼簡短且易於處理多測試用例重置。本題邊數上限 50,000，SPFA 完全足夠。

關鍵實現細節

圖的存儲：鏈式前向星

struct Edge { int to, w, next; } edges[MAXM];
int head[MAXN], cnt;
void addEdge(int u, int v, int w) {
    edges[cnt] = {v, w, head[u]};
    head[u] = cnt++;
}

雙向邊需調用兩次 addEdge。陣列大小預留 2*M。

SPFA 核心流程

void spfa(int s) {
    fill(dis, dis+n, INF);
    fill(inq, inq+n, false);
    dis[s] = 0;
    queue q; q.push(s); inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = head[u]; ~i; i = edges[i].next) {
            int v = edges[i].to;
            if (dis[v] > dis[u] + edges[i].w) {
                dis[v] = dis[u] + edges[i].w;
                if (!inq[v]) { q.push(v); inq[v] = true; }
            }
        }
    }
}

關鍵點：

• inq 標記防止重複入隊
• 距離更新才入隊，非單純 BFS
• 無需負環檢測（題目保證權重非負）

多測試用例重置

每個用例前 memset(head, -1, sizeof(head))，cnt = 0，避免殘留數據干擾。

複雜度分析

• 時間：平均 O(k·m)，k 為平均鬆弛輪數，實測極快
• 空間：O(n + m) 存圖 + O(n) 距離/隊列

常見坑點與優化

1. 輸入讀取：大數據量用 scanf 或關閉同步的 cin
2. 長整型：最大路徑 20,000 × 10,000 = 2e8，int 足夠，但建議用 long long 防溢出
3. SLF/LLL 優化：新節點入隊前與隊首比較，距離更小則插隊首（SLF），或定期將隊首移至隊尾（LLL），可顯著加速最壞情況
4. 不可達判斷：dis[t] == INF 輸出 "unreachable"

完整代碼框架

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 20005, MAXM = 100005;

struct Edge { int to, w, next; } e[MAXM];
int head[MAXN], dis[MAXN], cnt;
bool inq[MAXN];

void addEdge(int u, int v, int w) { ... }
void spfa(int s) { ... }

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        int n, m, S, T; cin >> n >> m >> S >> T;
        memset(head, -1, (n+1)*sizeof(int)); cnt = 0;
        while (m--) { int u,v,w; cin>>u>>v>>w; addEdge(u,v,w); addEdge(v,u,w); }
        spfa(S);
        cout << "Case #" << tc << ": ";
        if (dis[T] == INF) cout << "unreachable\n";
        else cout << dis[T] << '\n';
    }
    return 0;
}

舉一反三

掌握 SPFA 後，可嘗試：

• POJ 3259 Wormholes（負環檢測）
• UVa 10986 原題變體：K 短路、次短路
• 對比 Dijkstra + Fibonacci 堆在稠密圖上的優勢