有
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
TIP
帶有步數限制的最短路徑 — Bellman-Ford 天然支援限制鬆弛次數。
- 標準 Dijkstra 無法直接處理步數限制
- Bellman-Ford 做 k+1 輪鬆弛，恰好對應最多 k 個中轉站（k+1 條邊）
- 也可以用修改版 BFS，以層數控制步數
Approaches
1. BFS (level traversal) — O(V + E * K) / O(V + E)
- Idea: 按層做 BFS，每層代表多經過一站，最多做 k+1 層
- Time:
O(V + E * K) - Space:
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 (bounded rounds) — O(K * E) / O(V)
- Idea: 做 k+1 輪鬆弛，每輪用上一輪的結果避免串聯更新。天然支援步數限制。
- Time:
O(K * E) - Space:
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 限制鬆弛輪數
- Key trick: 每輪使用上一輪的
dist副本（dist.copyOf()）避免同一輪內的串聯更新，確保步數限制正確