Advanced Graphs Weighted shortest paths
473. Cheapest Flights Within K Stops
There are n cities, numbered from 0 to n - 1. You are given a list of one-way flights, where
flights[i] = [from, to, price] is a flight from city from to city to that costs price.
Return the lowest total price to travel from city src to city dst with at most k stops. If no route
makes it within k stops, return -1.
A stop is a city where you land and then take another flight. So a route with k stops uses k + 1
flights, and src and dst are not stops.
Example 1
Input: n = 5
flights = [[0, 1, 100],
[1, 2, 100],
[2, 4, 100],
[0, 3, 500],
[3, 4, 100],
[0, 4, 700]]
src = 0
dst = 4
k = 1
600Explanation: The route 0 → 1 → 2 → 4 costs only 300, but it has two stops. With at most one stop, the choices are 0 → 3 → 4 for 600 and the direct flight for 700.
Example 2
Input: n = 3
flights = [[0, 1, 50], [1, 2, 50]]
src = 0
dst = 2
k = 0
-1Explanation: The only route stops at city 1, and k = 0 allows no stops.
Example 3
Input: n = 4
flights = [[0, 1, 1000000000],
[1, 2, 1000000000],
[2, 3, 1000000000]]
src = 0
dst = 3
k = 2
3000000000Explanation: The only route takes three flights of 109 each and stops twice, which k = 2 allows.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ n ≤ 2000 ≤ flights.length ≤ 104flights[i] = [from, to, price], with0 ≤ from, to < n,from ≠ toand1 ≤ price ≤ 1090 ≤ src, dst < n0 ≤ k ≤ n- There can be more than one flight from one city to another, at different prices.
Clarifying questions
What you would ask an interviewer before writing any code.