POJ 3031 Big Christmas Tree：SPFA 求最短路徑加權總和

題目大意修正

原題描述易誤解。正確理解：給定無向圖，每個節點 i 有權重 W[i]，邊權為 w。求 每個節點到節點 1 的最短路徑距離 dis[i] × W[i] 的總和。若有節點無法到達 1，輸出 No Answer。

算法選擇：SPFA (Shortest Path Faster Algorithm)

圖中邊權非負，可用 Dijkstra，但 SPFA 寫法簡短、對負權邊也有韌性（本題無負權），且 n ≤ 50000, m ≤ 50000 時表現優異。

關鍵點

• 無向圖 → add(u,v,w); add(v,u,w);
• 距離和權重可能很大 → 用 long long (__int64)。
• 初始距離設 INF = 1e18。
• 隊列優化：inque[] 標記是否在隊列中，避免重複入隊。

完整程式碼（現代 C++ 風格）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;
const int MAXN = 50010;
const int MAXM = 50010;

struct Edge { int to; ll w; int next; };
Edge edges[2*MAXM];
int head[MAXN], ecnt;
ll W[MAXN], dis[MAXN];
bool inq[MAXN];
int n, m;

void init() {
    fill(head, head+n+1, -1);
    ecnt = 0;
}
void addEdge(int u, int v, ll w) {
    edges[ecnt] = {v, w, head[u]};
    head[u] = ecnt++;
}

void spfa() {
    queue q;
    fill(dis, dis+n+1, INF);
    fill(inq, inq+n+1, false);
    dis[1] = 0;
    q.push(1);
    inq[1] = true;
    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;
            ll w = edges[e].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        init();
        for (int i = 1; i <= n; ++i) cin >> W[i];
        for (int i = 0; i < m; ++i) {
            int u, v; ll w; cin >> u >> v >> w;
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        spfa();
        ll ans = 0;
        bool ok = true;
        for (int i = 2; i <= n; ++i) {
            if (dis[i] == INF) { ok = false; break; }
            ans += dis[i] * W[i];
        }
        if (ok) cout << ans << '\n';
        else cout << "No Answer\n";
    }
    return 0;
}

複雜度分析

• SPFA 平均 O(k·m)，k 為平均鬆弛輪數，通常很小。
• 最壞 O(n·m)，但隨機圖/無負環圖極快。
• 空間 O(n + m)。

常見坑點與修正

• 題目理解偏差：原以為是最小生成樹，實際是單源最短路徑加權和。
• 資料型別：dis[i] * W[i] 可能超過 32 位，必須用 64 位整數。
• 無向圖建雙向邊。
• 多測資初始化：每組測資需完整清空 head、dis、inq、ecnt。
• 輸出格式：No Answer 大小寫與空格完全一致。

為什麼不用 Dijkstra？

Dijkstra + 優先隊列同樣可行（O(m log n)），但 SPFA 代碼更短、無需 priority_queue、對稠密圖常數更小。本題邊數較多（5萬），SPFA 實測更快。

總結

POJ 3031 核心是單源最短路徑（SPFA/Dijkstra）+ 加權求和。關鍵在於正確理解題意、使用 64 位整數防溢位、無向圖建雙向邊。SPFA 實作簡潔高效，是此類題目的首選模板。