HDU 2544 最短路徑：Dijkstra 算法模板題詳解

題目背景

在成都街道圖中，標號 1 為商店，標號 N 為賽場。給定 M 條雙向道路及通行時間，求從商店到賽場的最短時間。多組測試數據，N ≤ 100，M ≤ 10000。

算法選擇：Dijkstra + 鄰接矩陣

節點數較小（≤100），鄰接矩陣儲存圖結構，配合 O(N²) 的 Dijkstra 實現足夠高效。

核心步驟

1. 初始化距離陣列 dis[] 為無窮大，dis[1] = 0。
2. 重複 N 次：選取未訪問且距離最小的節點 now，標記已訪問。
3. 鬆弛所有鄰接節點：if (dis[i] > dis[now] + map[now][i]) dis[i] = dis[now] + map[now][i]。
4. 答案為 dis[N]。

參考代碼 (C++)

#include <iostream>
#include <cstring>
#define INF 0x3f3f3f3f
#define MAXN 105
using namespace std;

int n, m;
int map[MAXN][MAXN];
int dis[MAXN];
bool vis[MAXN];

void dijkstra() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    for (int i = 1; i <= n; ++i) {
        int u = -1, minDist = INF;
        for (int j = 1; j <= n; ++j)
            if (!vis[j] && dis[j] < minDist) { minDist = dis[j]; u = j; }
        if (u == -1) break;
        vis[u] = true;
        for (int v = 1; v <= n; ++v)
            if (!vis[v] && map[u][v] < INF)
                dis[v] = min(dis[v], dis[u] + map[u][v]);
    }
}

int main() {
    while (cin >> n >> m, n || m) {
        memset(map, 0x3f, sizeof(map));
        for (int i = 0; i < m; ++i) {
            int u, v, w; cin >> u >> v >> w;
            map[u][v] = map[v][u] = min(map[u][v], w); // 保留最短邊
        }
        dijkstra();
        cout << dis[n] << '\n';
    }
    return 0;
}

關鍵細節

• 雙向圖，建圖時對稱賦值。
• 同一對節點可能有多條邊，取最小權重。
• 使用 0x3f3f3f3f 作為無窮大，配合 memset 快速初始化。
• 輸入以 0 0 結束，需正確處理多測試用例。

複雜度

時間 O(N²)，空間 O(N²)，完全滿足題目限制。