PAT 1030 Travel Plan：Dijkstra 求最短路徑並輸出路徑與費用

問題描述

給定 N (≤500) 個城市、M 條雙向公路（長度、費用），求從 S 到 D 的最短路徑；若最短路徑不唯一，選總費用最小者（保證唯一）。輸出路徑城市序列、總長度、總費用。

算法選擇：Dijkstra + 路徑記錄

N=500，鄰接矩陣 O(N²) Dijkstra 適合。需處理重邊：保留長度最小，長度相同保留費用最小。

關鍵數據結構

• dist[N][N], cost[N][N]：鄰接矩陣，初始化 INF。
• dis[N], pri[N]：源點到各點的最短距離、對應最小費用。
• path[N]：最短路徑中該點的前驅節點。
• vis[N]：是否已確定最短路。

Dijkstra 核心邏輯

for (int i = 0; i < N; i++) {
    int u = -1, minD = INF;
    for (int j = 0; j < N; j++)
        if (!vis[j] && dis[j] < minD) { minD = dis[j]; u = j; }
    if (u == -1) break;
    vis[u] = true;
    for (int v = 0; v < N; v++) if (!vis[v] && dist[u][v] < INF) {
        if (dis[u] + dist[u][v] < dis[v]) {
            dis[v] = dis[u] + dist[u][v];
            pri[v] = pri[u] + cost[u][v];
            path[v] = u;
        } else if (dis[u] + dist[u][v] == dis[v] && pri[u] + cost[u][v] < pri[v]) {
            pri[v] = pri[u] + cost[u][v];
            path[v] = u;
        }
    }
}

路徑重構與輸出

int stack[1000], top = 0;
for (int v = D; v != S; v = path[v]) stack[top++] = v;
stack[top++] = S;
while (top--) printf("%d ", stack[top]);  // 逆序輸出
printf("%d %d\n", dis[D], pri[D]);

完整 AC 代碼亮點

• 鄰接矩陣初始化對稱賦值。
• 重邊處理：if (d < dist[a][b]) update; else if (d == dist[a][b] && p < cost[a][b]) update;
• 路徑記錄 path[v] = u 在兩種更新情況下同步修改。
• 用數組模擬棧輸出路徑，避免遞歸棧溢出。

複雜度

• 時間：O(N²) = 2.5e5 操作，極快。
• 空間：O(N²) 矩陣 ≈ 1MB，符合限制。