HDU 2066 一個人的旅行：多源最短路，虛擬源點 + Dijkstra

問題描述

有 T 條雙向道路，連接城市（編號 1~1000）。草兒家在小鎮，與 S 個城市相鄰（可視為從家到這些城市距離為 0）。她想去 D 個目標城市之一。求從家出發到任一目標城市的最短時間。

建模：虛擬源點 0

引入虛擬節點 0 代表家。對每個相鄰城市 u，加邊 0 → u 權重 0。然後從 0 跑一次 Dijkstra，得到到所有城市的最短距離。答案為 min(dist[target])。

代碼實現（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;

int n, dist[MAXN];
bool vis[MAXN];
int g[MAXN][MAXN];

int dijkstra(int src, int N) {
    fill(dist, dist+N+1, INF);
    fill(vis, vis+N+1, false);
    dist[src] = 0;
    for (int i = 0; i <= N; ++i) {
        int u = -1, best = INF;
        for (int j = 0; j <= N; ++j)
            if (!vis[j] && dist[j] < best) { best = dist[u=j]; }
        if (u == -1) break;
        vis[u] = true;
        for (int v = 0; v <= N; ++v)
            if (dist[v] > dist[u] + g[u][v])
                dist[v] = dist[u] + g[u][v];
    }
    return 0;
}

int main() {
    int T, S, D;
    while (scanf("%d%d%d", &T, &S, &D) == 3) {
        memset(g, 0x3f, sizeof(g));
        int maxV = 0;
        for (int i = 0; i < T; ++i) {
            int a, b, w; scanf("%d%d%d", &a, &b, &w);
            if (w < g[a][b]) g[a][b] = g[b][a] = w;
            maxV = max(maxV, max(a, b));
        }
        for (int i = 1; i <= S; ++i) {
            int u; scanf("%d", &u);
            g[0][u] = g[u][0] = 0; // 虛擬源點 0
            maxV = max(maxV, u);
        }
        int target[1005];
        for (int i = 1; i <= D; ++i) scanf("%d", &target[i]);
        dijkstra(0, maxV);
        int ans = INF;
        for (int i = 1; i <= D; ++i) ans = min(ans, dist[target[i]]);
        printf("%d\n", ans);
    }
    return 0;
}

優化點

• 只需跑一次 Dijkstra，而非對每個目標跑 S 次。
• 處理重邊：保留最小權重。
• 城市編號不連續，用 maxV 確定數組範圍。

複雜度

Dijkstra O(V^2)，V ≤ 1000，極快。