UVA 10801 Lift Hopping：最短路含換乘等待時間

問題描述

• n 部電梯，每部有運行速度 t[i]（層/秒），停靠樓層集合 S_i。
• 從樓層 0 到目標樓層 k，可在電梯間換乘，換乘需額外 60 秒等待，但首次乘電梯不等待。
• 求最短到達時間。

建模為圖最短路

• 節點：樓層（0..100）。
• 邊：同一部電梯內任意兩停靠樓層 u, v，權重 |u-v| * t[i]。
   為處理換乘等待，狀態擴展為 (樓層, 電梯ID)，或在鬆弛時判斷是否換乘。

狀態擴展法（推薦）

狀態 (floor, lastElev)，lastElev = -1 表示未乘電梯。
優先隊列 Dijkstra：

• 從 (0, -1) 出發，距離 0。
• 對當前狀態 (u, e)，遍歷所有電梯 i 及其停靠樓層 v：
   若 i == e，新距離 = d + |u-v|*t[i]。
   若 i != e，新距離 = d + |u-v|*t[i] + (e==-1?0:60)。
• 目標：任意 (k, *) 的最小距離。

關鍵代碼

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct State { int d, floor, elev; bool operator<(State o) const { return d > o.d; } };

int main() {
    int n, k;
    while (cin >> n >> k) {
        vector t(n);
        vector> stops(n);
        for (int i = 0; i < n; ++i) cin >> t[i];
        string line; getline(cin, line); // 吃換行
        for (int i = 0; i < n; ++i) {
            getline(cin, line);
            stringstream ss(line);
            int f; while (ss >> f) stops[i].push_back(f);
        }
        // 樓層 0..100，電梯 -1..n-1 映射為 0..n
        vector> dist(101, vector(n+1, INF));
        priority_queue pq;
        dist[0][n] = 0; // elev = n 代表 -1
        pq.push({0, 0, n});
        int ans = -1;
        while (!pq.empty()) {
            auto cur = pq.top(); pq.pop();
            if (cur.d != dist[cur.floor][cur.elev]) continue;
            if (cur.floor == k) { ans = cur.d; break; }
            for (int i = 0; i < n; ++i) {
                for (int v : stops[i]) {
                    int nd = cur.d + abs(cur.floor - v) * t[i];
                    if (cur.elev != n && i != cur.elev) nd += 60;
                    int ne = i;
                    if (nd < dist[v][ne]) {
                        dist[v][ne] = nd;
                        pq.push({nd, v, ne});
                    }
                }
            }
        }
        if (ans == -1) cout << "Impossible\n";
        else cout << ans << "\n";
    }
}

複雜度

• 狀態數 ≤ 101 × 6 ≈ 600。
• 邊數 ≤ 狀態數 × 總停靠點，極小。
• Dijkstra O(E log V) 瞬間通過。