HDU 1535 Invitation Cards：雙向 Dijkstra 求有向圖雙向最短路之和

問題：有向圖，節點 1 向 2..n 派發邀請函並收回。求所有節點往返（1→i 和 i→1）最短路長度之和。n, m ≤ 100,000。

關鍵洞察：反向建圖轉單源

• 1 → 所有點：原圖跑一次 Dijkstra，得 dist1[i]；
• 所有點 → 1：反向建圖（邊 u→v 變 v→u），以 1 為源跑 Dijkstra，得 dist2[i]（即原圖中 i→1 的最短路）；
• 答案 = Σ_i=2..n (dist1[i] + dist2[i])。

代碼框架

struct Edge { int u, v, w; };
vector edges;
vector G[MAXN];
int dist[MAXN]; bool vis[MAXN];

void Dijkstra() {
    fill(dist, dist+n+1, INF); fill(vis, vis+n+1, false);
    dist[1] = 0;
    priority_queue Q;
    Q.push({1, 0});
    while (!Q.empty()) {
        auto cur = Q.top(); Q.pop();
        if (vis[cur.u]) continue;
        vis[cur.u] = true;
        for (auto& e : G[cur.u]) {
            if (dist[e.v] > cur.d + e.w) {
                dist[e.v] = cur.d + e.w;
                Q.push({e.v, dist[e.v]});
            }
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        edges.clear();
        for (int i = 0; i < m; i++) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            edges.push_back({u, v, w});
        }
        long long ans = 0;
        // 正向
        for (int i = 1; i <= n; i++) G[i].clear();
        for (auto& e : edges) G[e.u].push_back({e.u, e.v, e.w});
        Dijkstra();
        for (int i = 2; i <= n; i++) ans += dist[i];
        // 反向
        for (int i = 1; i <= n; i++) G[i].clear();
        for (auto& e : edges) G[e.v].push_back({e.v, e.u, e.w});
        Dijkstra();
        for (int i = 2; i <= n; i++) ans += dist[i];
        printf("%lld\n", ans);
    }
}

複雜度

• 兩次 Dijkstra：O((V+E) log V)；
• 總體 O(T · (V+E) log V)，滿足大規模圖要求。

反向建圖是處理「多點到單點最短路」的標準技巧，將多源問題轉化為單源問題。