UVA 1048 Low Cost Air Travel：狀態圖最短路與城市哈希映射

UVA 1048 Low Cost Air Travel：狀態圖最短路與城市哈希映射

給定多張聯程機票 (每張包含多個城市序列及價格) 及若干行程，求完成行程的最小費用。城市編號較大需哈希映射。

建模：狀態節點

• 節點 (i, city)：表示已完成行程前 i 個城市，當前位於 city。
• 起點：(0, start_city)，終點：(k, end_city) (k 為行程城市數)。
• 邊：使用第 t 張機票從其起始城市出發，按序飛行至該機票覆蓋的行程城市，費用為機票價格。一張機票可拆解為多條邊 (每段飛行)。

Dijkstra 算法

標準堆優化 Dijkstra，節點數 ≤ 行程長度 × 不同城市數，邊數 ≤ 機票數 × 機票城市數 × 行程長度。使用 map 將城市編號壓縮為 0-based 索引。

關鍵代碼片段

struct Edge { int u, v, cost, id; };
struct HeapNode { int d, u; bool operator<(HeapNode o) const { return d > o.d; } };

struct Dijkstra {
    // ... 標準實現：init, add_edge, dijkstra ...
    void dijkstra(int s) {
        priority_queue pq;
        fill(d, d+n, INF); d[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            auto [du, u] = pq.top(); pq.pop();
            if (du != d[u]) continue;
            for (int i = head[u]; ~i; i = nxt[i]) {
                int v = edges[i].v, w = edges[i].cost;
                if (d[v] > du + w) {
                    d[v] = du + w;
                    p[v] = i;
                    pq.push({d[v], v});
                }
            }
        }
    }
};

坑點提示

• 城市編號稀疏大範圍，必須哈希壓縮 (unordered_map 或 map)。
• 機票可重複使用？不，題目隱含每張機票用於一次行程段，建模時每張機票對應一組邊。
• 輸出需包含使用的機票序列，需記錄前驅邊 p[] 回溯。