HDU 2066 一個人的旅行：多源多汇最短路（Dijkstra 變體）

問題建模

• T 條雙向邊，城市編號 1~1000。
• S 個起點城市（家相鄰），距離視為 0。
• D 個目標城市，求從任一起點到任一目標的**最短路徑長度**。

關鍵處理

1. **超級源點**：虛擬節點 0，向每個起點連邊權 0，單源最短路即可。
2. **並行邊保留最小權**：map[u][v] = min(map[u][v], w)。
3. **初始化距離**：dist[i] = INF; dist[0] = 0。
4. **Dijkstra 模板**：鄰接矩陣版（N≤1000 適用）。
5. **答案提取**：遍歷所有目標城市，取 min(dist[target])。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXV = 1005;

int dist[MAXV], graph[MAXV][MAXV];
bool vis[MAXV];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, S, D;
    while (cin >> T >> S >> D) {
        // 初始化
        fill(&graph[0][0], &graph[0][0] + MAXV*MAXV, INF);
        for (int i = 0; i < MAXV; ++i) graph[i][i] = 0;

        // 讀入邊
        for (int i = 0, a, b, t; i < T; ++i) {
            cin >> a >> b >> t;
            graph[a][b] = graph[b][a] = min(graph[a][b], t);
        }

        // 超級源點 0 連接起點
        for (int i = 0, x; i < S; ++i) {
            cin >> x;
            graph[0][x] = graph[x][0] = 0;
        }

        // 讀入目標
        vector targets(D);
        for (int i = 0; i < D; ++i) cin >> targets[i];

        // Dijkstra
        fill(dist, dist + MAXV, INF);
        fill(vis, vis + MAXV, false);
        dist[0] = 0;
        for (int iter = 0; iter <= 1000; ++iter) {
            int u = -1, best = INF;
            for (int i = 0; i <= 1000; ++i)
                if (!vis[i] && dist[i] < best) best = dist[u = i];
            if (u == -1) break;
            vis[u] = true;
            for (int v = 0; v <= 1000; ++v)
                if (!vis[v] && graph[u][v] < INF)
                    dist[v] = min(dist[v], dist[u] + graph[u][v]);
        }

        // 答案
        int ans = INF;
        for (int t : targets) ans = min(ans, dist[t]);
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(V²) = 10⁶，完全滿足 1s 時限。