HDU 1535：雙向 SPFA 解決有向圖雙向最短路徑和

HDU 1535：給定有向圖，求從節點 1 到所有其他節點的最短路徑和，加上從所有節點到節點 1 的最短路徑和。

核心思路：正向圖 + 反向圖

1. 建立正向圖：按輸入邊方向存儲
2. 建立反向圖：所有邊反向存儲
3. 在正向圖上從源點 1 跑 SPFA，得 dist1[v] = 1 → v 最短距離
4. 在反向圖上從源點 1 跑 SPFA，得 dist2[v] = v → 1 最短距離（等價於原圖 v→1）
5. 答案 = Σ(dist1[i] + dist2[i])，i=2..n

SPFA 算法實現

const int INF = 0x3f3f3f3f;
struct Edge { int to, w, next; };
vector<Edge> edges;
vector<int> head;

void add_edge(int u, int v, int w) {
    edges.push_back({v, w, head[u]});
    head[u] = edges.size() - 1;
}

void spfa(int src, vector<int>& dist) {
    int n = head.size() - 1;
    dist.assign(n + 1, INF);
    vector<bool> inq(n + 1, false);
    queue<int> q;
    
    dist[src] = 0;
    q.push(src);
    inq[src] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            int w = edges[i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}

完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;

struct Edge { int to, w, next; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        
        vector<Edge> edges_f, edges_r;
        vector<int> head_f(n+1, -1), head_r(n+1, -1);
        
        auto add_f = [&](int u, int v, int w) {
            edges_f.push_back({v, w, head_f[u]});
            head_f[u] = edges_f.size() - 1;
        };
        auto add_r = [&](int u, int v, int w) {
            edges_r.push_back({v, w, head_r[u]});
            head_r[u] = edges_r.size() - 1;
        };
        
        for (int i = 0; i < m; ++i) {
            int a, b, c; cin >> a >> b >> c;
            add_f(a, b, c);
            add_r(b, a, c); // 反向邊
        }
        
        auto spfa = [&](int src, const vector<int>& head, const vector<Edge>& edges) {
            vector<int> dist(n+1, INF);
            vector<bool> inq(n+1, false);
            queue<int> q;
            dist[src] = 0; q.push(src); inq[src] = true;
            
            while (!q.empty()) {
                int u = q.front(); q.pop();
                inq[u] = false;
                for (int i = head[u]; i != -1; i = edges[i].next) {
                    int v = edges[i].to, w = edges[i].w;
                    if (dist[v] > dist[u] + w) {
                        dist[v] = dist[u] + w;
                        if (!inq[v]) { q.push(v); inq[v] = true; }
                    }
                }
            }
            return dist;
        };
        
        auto dist1 = spfa(1, head_f, edges_f); // 1 -> v
        auto dist2 = spfa(1, head_r, edges_r); // v -> 1 (反向圖 1 -> v)
        
        long long ans = 0;
        for (int i = 2; i <= n; ++i) ans += dist1[i] + dist2[i];
        cout << ans << '\n';
    }
    return 0;
}

關鍵優化點

1. 鄰接表存儲：邊數最多 1e6，靜態陣列或 vector 均可
2. SLF/LLL 優化：SPFA 入隊優化（Small Label First / Large Label Last），防退化
3. 雙圖複用：邊數組分離，避免重複建圖開銷
4. 長長整型累加：答案可能超 int，用 long long

複雜度分析

• SPFA 平均 O(k·m)，k 為平均鬆弛次數，通常極小
• 兩次 SPFA：O(m) 期望
• 空間：O(n + m)

替代算法：Dijkstra + 堆

邊權非負時，Dijkstra 更穩定：O(m log n)，無負環風險。本題邊權為正，可用 Dijkstra。

總結

• 「從所有點到 1」等價於「反向圖從 1 到所有點」
• 雙向最短路和問題，標準套路：正向圖 + 反向圖
• SPFA 實現簡短，適用於邊權可能為負或稠密圖；Dijkstra 更適合非負邊權

此題是「多源/匯點最短路轉換」的經典範例，掌握反向圖技巧，能秒殺大量類似問題。