POJ 2502 Subway 地鐵最短路徑 (Dijkstra 算法)

問題背景

你從安靜的郊區搬到大城市，上學需結合步行與搭乘地鐵。步行速度 10 km/h，地鐵速度 40 km/h。假設到達車站即有班車可搭乘，可任意換乘路線。給定家與學校的坐標，以及多條地鐵路線的站點座標（每條路線至少兩站，站點間直線行駛），求從家到學校的最短時間（分鐘，四捨五入）。

解題策略

• 建圖：將家、學校、所有地鐵站視為節點。任意兩節點間若無地鐵直達，以步行速度計算邊權（時間）；同一地鐵線上相鄰站點間以地鐵速度計算邊權。
• 最短路徑：因所有邊權為正，適用 Dijkstra 算法求從家（源點）到學校（終點）的最短時間。
• 輸入處理：以 EOF 結束，每條地鐵線以 -1 -1 結束。總站點數 ≤ 200。

關鍵數據結構

struct Point { double x, y; };
const int MAXN = 400;
double dist[MAXN];       // 到起點的最短距離
bool vis[MAXN];          // 是否已確定最短路徑
double graph[MAXN][MAXN]; // 鄰接矩陣存儲時間權重
Point stops[MAXN];       // 所有節點座標

核心代碼片段 (Dijkstra)

void Dijkstra(int src, int n) {
    fill(dist, dist + n, 1e100);
    fill(vis, vis + n, false);
    dist[src] = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        double best = 1e100;
        for (int j = 0; j < n; ++j)
            if (!vis[j] && dist[j] < best) best = dist[u = j];
        if (u == -1) break;
        vis[u] = true;
        for (int v = 0; v < n; ++v)
            if (!vis[v] && graph[u][v] < 1e100)
                dist[v] = min(dist[v], dist[u] + graph[u][v]);
    }
}

複雜度

節點數 N ≤ 202，Dijkstra 用鄰接矩陣實現為 O(N²)，完全足夠。

注意事項

1. 座標單位為公尺，速度需換算為公尺/分鐘：步行 10 km/h = 10000/60 m/min，地鐵 40 km/h = 40000/60 m/min。
2. 輸出須四捨五入到整數分鐘。
3. 家與學校也視為圖中的節點，編號分別為 0 和 1。