HDU 2680 Choose the best route：超級源點 + Dijkstra 求多起點到單終點最短路

題目模型

有向圖，n 點 m 邊，終點固定為 s。給定 w 個起點，求任一起點到 s 的最短路長度。n < 1000, m < 20000。

超級源點技巧

引入虛擬節點 0，向所有 w 個起點連邊權為 0。從 0 跑一次 Dijkstra，即可得到所有點到超級源點的最短距離，因為反向邊權為 0，dis[s] 即為原圖中任一起點到 s 的最短距離。若 dis[s] == INF 輸出 -1。

代碼實現要點

• 鄰接矩陣 map[1010][1010] 初始化 INF，讀入邊取最小權
• Dijkstra 模板：dis[0]=0，其餘 INF；每輪選未訪問最小 dis 點鬆弛
• 最後直接輸出 dis[s]（或 -1）

精簡 AC 代碼

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
int map[1010][1010], dis[1010], mark[1010], n;

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

int main() {
    int m,s,w;
    while(scanf("%d%d%d",&n,&m,&s)!=EOF) {
        for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) map[i][j]=INF;
        for(int i=0;i<m;++i) {
            int p,q,t; scanf("%d%d%d",&p,&q,&t);
            if(map[p][q]>t) map[p][q]=t;
        }
        scanf("%d",&w);
        for(int i=0;i<w;++i) { int x; scanf("%d",&x); map[0][x]=0; } // 超級源點
        dijkstra();
        printf("%d\n", dis[s]==INF ? -1 : dis[s]);
    }
    return 0;
}