HDOJ Choose the best route：反向建圖 + Dijkstra 求多源最短路徑

題目大意

琪琪想拜訪朋友但暈車，需找出從家附近多個起點站到朋友家附近唯一終點站的最少花費時間。給定有向圖，站點編號 1~n，m 條單向邊，每條邊有耗時。輸入 w 個起點站，求任一起點到終點的最短時間，不可達輸出 -1。

解題思路：反向建圖化多源為單源

直接從多個起點跑 Dijkstra 會 TLE。關鍵洞察：將終點作為起點，反向構建圖，跑一次 Dijkstra 即可得到所有點到原終點的最短距離，最後在 w 個起點中取最小值。因為是有向圖，反向建圖時邊方向須翻轉：原邊 p → q 變為 q → p。

關鍵實現細節

• 鄰接矩陣初始化：對角線 0，其餘 INF（0x3f3f3f3f）
• 讀入邊時：if (map[b][a] > cost) map[b][a] = cost; 過濾重邊並反向存儲
• Dijkstra 模板：vis[] 標記，dis[] 記錄距離，每輪選未訪問最小距離點鬆弛鄰邊
• 最後遍歷 w 個起點，取 dis[start] 最小值，若為 INF 輸出 -1

AC 參考代碼

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f

int vis[1010], map[1010][1010], dis[1010], n, ans[1010], num, beg;

void init() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            map[i][j] = (i == j) ? 0 : INF;
}

void dijkstra() {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i) dis[i] = map[beg][i];
    vis[beg] = 1;
    for (int i = 1; i <= n; ++i) {
        int key = -1, temp = INF;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && temp > dis[j]) temp = dis[key = j];
        if (temp == INF) break;
        vis[key] = 1;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && dis[j] > dis[key] + map[key][j])
                dis[j] = dis[key] + map[key][j];
    }
}

int main() {
    int m;
    while (scanf("%d%d%d", &n, &m, &beg) != EOF) {
        memset(ans, 0x3f, sizeof(ans));
        init();
        for (int i = 1; i <= m; ++i) {
            int a, b, cost; scanf("%d%d%d", &a, &b, &cost);
            if (map[b][a] > cost) map[b][a] = cost; // 反向建圖
        }
        scanf("%d", &num);
        dijkstra();
        int res = INF;
        for (int i = 0; i < num; ++i) {
            int s; scanf("%d", &s);
            if (dis[s] < res) res = dis[s];
        }
        printf("%d\n", res == INF ? -1 : res);
    }
    return 0;
}