LeetCode Entry
787. Cheapest Flights Within K Stops
Cheapest travel src -> dst with at most k stops in a directed weighted graph.
787. Cheapest Flights Within K Stops medium blog post substack youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/516
Problem TLDR
Cheapest travel src -> dst with at most k stops in a directed weighted graph.
Approach
There is a Floyd-Warshall algorithm for such problems: make k rounds of travel trough all the reachable edges and improve the so-far cost.
- we must make a copy of the previous step, to avoid flying more than one step in a round
Complexity
-
Time complexity: \(O(kne)\), where
eis edges -
Space complexity: \(O(n)\)
Code
fun findCheapestPrice(n: Int, flights: Array<IntArray>, src: Int, dst: Int, k: Int): Int {
val costs = IntArray(n) { Int.MAX_VALUE / 2 }
costs[src] = 0
repeat(k + 1) {
val prev = costs.clone()
for ((f, t, c) in flights)
costs[t] = min(costs[t], prev[f] + c)
}
return costs[dst].takeIf { it < Int.MAX_VALUE / 2 } ?: -1
}
pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
let mut costs = vec![i32::MAX / 2 ; n as usize];
costs[src as usize] = 0;
for _ in 0..=k {
let prev = costs.clone();
for e in &flights {
costs[e[1] as usize] = costs[e[1] as usize].min(prev[e[0] as usize] + e[2])
}
}
if costs[dst as usize] < i32::MAX / 2 { costs[dst as usize] } else { -1 }
}