HDU 2066 一個人的旅行：多源最短路 SPFA

問題描述

給定無向圖，T 條邊，S 個起點，D 個終點。求任意起點到任意終點的最短距離。

超級源點技巧

新增虛擬節點 0，向每個起點連邊權 0 的有向邊。
從 0 跑一次 SPFA（或 Dijkstra），得到所有點的最短距離，再取終點中的最小值。

SPFA 實現

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 10010, MAXM = 200020;
struct Edge { int to, w, nxt; } e[MAXM];
int head[MAXN], ecnt;
void addEdge(int u, int v, int w) {
    e[ecnt] = {v, w, head[u]}; head[u] = ecnt++;
}
int dis[MAXN]; bool inq[MAXN];
void spfa(int s, int n) {
    fill(dis, dis+n+1, INF); fill(inq, inq+n+1, false);
    queue<int> q; q.push(s); dis[s] = 0; inq[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (!inq[v]) { q.push(v); inq[v] = true; }
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T, S, D;
    while (cin >> T >> S >> D) {
        fill(head, head+MAXN, -1); ecnt = 0;
        for (int i = 0; i < T; ++i) {
            int u, v, w; cin >> u >> v >> w;
            addEdge(u, v, w); addEdge(v, u, w);
        }
        int super = 0;
        for (int i = 0; i < S; ++i) {
            int s; cin >> s; addEdge(super, s, 0);
        }
        vector<int> dest(D);
        for (int &x : dest) cin >> x;
        spfa(super, 10000);
        int ans = INF;
        for (int x : dest) ans = min(ans, dis[x]);
        cout << ans << '\n';
    }
    return 0;
}

複雜度

SPFA 平均 O(E)，最壞 O(VE)；本題圖規模中等，SPFA 足夠。也可用 Dijkstra + 堆優化到 O(E log V)。