POJ 1511 Invitation Cards：雙向最短路之和 (Dijkstra + 鄰接表優化)

問題描述

有向圖，P 個站點 (1 為中心站 CCS)，Q 條單向邊。每天志願者從 1 出發去各站點，晚上再從各站點回 1。求每天總車費最小值（即 1 到所有點最短路之和 + 所有點到 1 最短路之和）。P, Q ≤ 1,000,000。

解法

1. 建立正向圖與反向圖（或建一張圖，跑兩次 Dijkstra：一次原圖，一次反圖）。
2. 使用鄰接表存儲邊（結構體數組 + head 指針），避免 vector 開銷。
3. Dijkstra + 優先隊列 (小根堆) 求單源最短路。
4. 兩次距離和即為答案。

關鍵優化

• 邊數 1e6，用靜態數組存邊：to, w, next，head[u] 指向第一條邊索引。
• 避免 vector 動態分配與清理導致 TLE。
• 用 pair 進堆，或自定義結構體。

複雜度

• 時間：O((P+Q) log P) 兩次。
• 空間：O(P+Q)。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;

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

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

ll dijkstra(int n, int s) {
    vector dis(n+1, INF);
    vector vis(n+1, 0);
    priority_queue, vector>, greater>> pq;
    dis[s] = 0; pq.emplace(0, s);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i=head[u]; ~i; i=e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > d + w) {
                dis[v] = d + w;
                pq.emplace(dis[v], v);
            }
        }
    }
    ll sum = 0;
    for (int i=1;i<=n;i++) sum += dis[i];
    return sum;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int P, Q; cin >> P >> Q;
        fill(head+1, head+P+1, -1); ecnt = 0;
        vector> edges;
        edges.reserve(Q);
        for (int i=0;i>u>>v>>w;
            edges.emplace_back(u,v,w);
            add_edge(u,v,w);
        }
        ll ans1 = dijkstra(P, 1);
        // 反向圖
        fill(head+1, head+P+1, -1); ecnt = 0;
        for (auto [u,v,w] : edges) add_edge(v,u,w);
        ll ans2 = dijkstra(P, 1);
        cout << ans1 + ans2 << '\n';
    }
    return 0;
}