MediumRating 1786

787. Cheapest Flights Within K Stops

dynamic-programmingdepth-first-searchbreadth-first-searchgraphheap-priority-queueshortest-path

解題說明

Cheapest Flights Within K Stops（787）

題目描述：有 n 個城市和 m 條單向航班。每條航班有起點、終點和費用。給定起點 src、終點 dst，以及最多可停靠 k 個中間站（即最多搭乘 k+1 段航班），求從 src 到 dst 的最低費用。若無法到達則回傳 -1。

解題思路：本題使用 Bellman-Ford 演算法的變形，限制鬆弛輪數為 k+1 輪（對應最多 k+1 段航班，即最多 k 個中間停靠站）。

核心技巧：每一輪鬆弛必須使用上一輪的距離陣列（而非當前輪的），否則一輪內可能使用多條邊，等同於走了超過一段路。具體做法是在每輪開始時複製當前 dist 陣列為 prev，所有鬆弛計算都以 prev 為基準。

演算法步驟：

初始化 dist 陣列為無窮大，dist[src] = 0。
進行 k+1 輪鬆弛：
- 複製 dist 為 prev。
- 對所有邊 (u, v, w)，若 prev[u] != INF，則嘗試更新 dist[v] = min(dist[v], prev[u] + w)。
最終若 dist[dst] == INF 則回傳 -1，否則回傳 dist[dst]。

時間複雜度 O(K × E)，空間複雜度 O(V)，非常高效。

C++ 解法

複雜度分析

時間複雜度：O(K × E) — 共進行 k+1 輪鬆弛，每輪遍歷所有 E 條邊，其中 E 為航班數量。

空間複雜度：O(V) — 僅使用兩個長度為 n 的距離陣列（dist 與 prev），V 為城市數量。

虛擬碼

1. Initialize dist[0..n-1] = INF, dist[src] = 0.
2. Repeat (k+1) times:
   a. prev = copy of dist  // freeze current state
   b. For each flight (u, v, w):
      - If prev[u] != INF and prev[u] + w < dist[v]:
        - dist[v] = prev[u] + w
3. If dist[dst] == INF, return -1.
4. Return dist[dst].

其他解法

Dijkstra + 停靠站計數 O((V + E) log V)：在 Dijkstra 中，狀態為 (cost, node, stops_used)，只要 stops_used ≤ k 就可以繼續擴展。用最小堆按 cost 排序。此方法在稀疏圖上更快，但需要注意同一節點可能以不同的停靠數抵達，不能直接用 visited 陣列剪枝，需允許更少停靠數的路徑重新入堆。

BFS（層次搜尋）O(K × E)：等同於 Bellman-Ford 的直觀版本，每輪 BFS 相當於一段航班，共進行 k+1 輪，記錄每個節點的最低費用。邏輯與 Bellman-Ford 相同但以 BFS 佇列實作，可讀性更高。

延伸思考

若每條航班有不同的時間成本，且我們希望在費用不超過預算的前提下最小化總飛行時間，應如何修改演算法？
若允許在同一城市停留（即一個停靠站可以不移動），問題的答案會改變嗎？為什麼？
如果需要輸出具體的飛行路線（而非僅費用），如何修改 Bellman-Ford 來追蹤前驅節點？