Cheapest Flights Within K Stops
MediumGraphs · Airbnb
There are n cities labelled 0 to n - 1. Each entry flights[i] = [from_i, to_i, price_i] is a one-way flight from city from_i to city to_i that costs price_i.
Return the lowest total price to travel from city src to city dst with at most k stops. A stop is any city you pass through between src and dst, so a route with at most k stops uses at most k + 1 flights. If no route satisfies the limit, return -1.
Example 1
- Input:
- n = 5, flights = [[0, 1, 3], [1, 4, 3], [0, 2, 1], [2, 3, 1], [3, 4, 1], [0, 4, 10]], src = 0, dst = 4, k = 1
- Output:
- 6
- Explanation
- The cheapest route overall is 0 -> 2 -> 3 -> 4 for 3, but it stops at two cities. With one stop allowed, the best is 0 -> 1 -> 4 for 3 + 3 = 6, which beats the direct flight costing 10.
Example 2
- Input:
- n = 5, flights = [[0, 1, 3], [1, 4, 3], [0, 2, 1], [2, 3, 1], [3, 4, 1], [0, 4, 10]], src = 0, dst = 4, k = 2
- Output:
- 3
- Explanation
- Now two stops are allowed, so 0 -> 2 -> 3 -> 4 for 1 + 1 + 1 = 3 is legal and cheapest.
Example 3
- Input:
- n = 3, flights = [[0, 1, 2], [1, 0, 2]], src = 0, dst = 2, k = 1
- Output:
- -1
- Explanation
- No flight lands in city 2, so it cannot be reached at all.
Constraints
1 <= n <= 1000 <= flights.length <= n * (n - 1) / 2flights[i].length == 30 <= from_i, to_i < nandfrom_i != to_i1 <= price_i <= 10^4- There is at most one flight from any city to any other city
0 <= src, dst, k < nandsrc != dst