787. Cheapest Flights Within K Stops

Medium
Description

有 n 個城市和一些航班 flights[i] = [from, to, price]。給定起點 src、終點 dst 和最多經停 k 站的限制，回傳最便宜的票價。若無法到達回傳 -1。

Example:

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 Output: 700

Intuition#

帶有步數限制的最短路徑 – Bellman-Ford 天然支援限制鬆弛次數。

  • 標準 Dijkstra 無法直接處理步數限制
  • Bellman-Ford 做 k+1 輪鬆弛，恰好對應最多 k 個中轉站（k+1 條邊）
  • 也可以用修改版 BFS，以層數控制步數

Approaches#

1: BFS（層級遍歷）#

  • 概念: 按層做 BFS，每層代表多經過一站，最多做 k+1 層
  • 時間複雜度: O(V + E * K)
  • 空間複雜度: O(V + E)
class Solution {
    fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
        val graph = Array(n) { mutableListOf<IntArray>() }
        for ((from, to, price) in flights) {
            graph[from].add(intArrayOf(to, price))
        }

        val dist = IntArray(n) { Int.MAX_VALUE }
        dist[src] = 0
        val queue: ArrayDeque<IntArray> = ArrayDeque() // [node, cost]
        queue.add(intArrayOf(src, 0))
        var stops = 0

        while (queue.isNotEmpty() && stops <= k) {
            val size = queue.size
            repeat(size) {
                val (u, costU) = queue.removeFirst()
                for ((v, price) in graph[u]) {
                    val newCost = costU + price
                    if (newCost < dist[v]) {
                        dist[v] = newCost
                        queue.add(intArrayOf(v, newCost))
                    }
                }
            }
            stops++
        }

        return if (dist[dst] == Int.MAX_VALUE) -1 else dist[dst]
    }
}

⭐2: Bellman-Ford（限制輪數）#

  • 概念: 做 k+1 輪鬆弛，每輪用上一輪的結果避免串聯更新。天然支援步數限制。
  • 時間複雜度: O(K * E)
  • 空間複雜度: O(V)
class Solution {
    fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
        var dist = IntArray(n) { Int.MAX_VALUE }
        dist[src] = 0

        repeat(k + 1) {
            val temp = dist.copyOf()
            for ((from, to, price) in flights) {
                if (dist[from] != Int.MAX_VALUE && dist[from] + price < temp[to]) {
                    temp[to] = dist[from] + price
                }
            }
            dist = temp
        }

        return if (dist[dst] == Int.MAX_VALUE) -1 else dist[dst]
    }
}

🔑 Takeaways#

  • Pattern: 帶步數限制的最短路徑 – Bellman-Ford 限制鬆弛輪數
  • 關鍵技巧: 每輪使用上一輪的 dist 副本（dist.copyOf()）避免同一輪內的串聯更新，確保步數限制正確