Mid/SeniorBreadth-First SearchDepth-First SearchDynamic ProgrammingGraph TheoryHeap (Priority Queue)Shortest Path
Cheapest Flights Within K Stops
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
Example 1
Input
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1Output
700The optimal path with at most 1 stop from city 0 to 3 has cost 100 + 600 = 700, while the cheaper path through cities [0,1,2,3] is invalid because it uses 2 stops.
Example 2
Input
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1Output
200The optimal path with at most 1 stop from city 0 to 2 has cost 100 + 100 = 200.
Constraints
- 2 <= n <= 100
- 0 <= flights.length <= (n * (n - 1) / 2)
- flights[i].length == 3
- 0 <= fromi, toi < n
- fromi != toi
- 1 <= pricei <= 10^4
- There will not be any multiple flights between two cities.
- 0 <= src, dst, k < n
- src != dst