751. Cheap Flights, Few Stops
A regional carrier sells connecting tickets between n airports numbered 0 to n - 1. Each entry flights[i] = [from, to, price] is a one-directional flight. A traveller wants to get from src to dst and will change planes at most k times, that is, make at most k intermediate stops (so at most k + 1 flights).
Return the lowest total price of such an itinerary, or -1 if no itinerary with at most k stops exists. Several flights may connect the same pair of airports, and an itinerary may pass through an airport more than once if that still respects the stop limit.
Example 1
- Input:
- n = 5flights = [[0,1,50],[1,2,40],[2,4,30],[0,3,200],[3,4,60],[1,4,150]]src = 0dst = 4k = 1
- Output:
- 200
- Explanation:
With one stop the options are 0-1-4 for 200 and 0-3-4 for 260; the cheaper chain 0-1-2-4 needs two stops.
Example 2
- Input:
- n = 5flights = [[0,1,50],[1,2,40],[2,4,30],[0,3,200],[3,4,60],[1,4,150]]src = 0dst = 4k = 2
- Output:
- 120
- Explanation:
Two stops allow 0-1-2-4 for 50 + 40 + 30 = 120, the cheapest of all itineraries.
Example 3
- Input:
- n = 5flights = [[0,1,50],[1,2,40],[2,4,30],[0,3,200],[3,4,60],[1,4,150]]src = 0dst = 4k = 0
- Output:
- -1
- Explanation:
No direct flight from airport 0 to airport 4 exists, so with zero stops the answer is -1.
Constraints
- 2 ≤ n ≤ 500
- 0 ≤ flights.length ≤ 5000
- 0 ≤ from, to < n and from ≠ to
- 1 ≤ price ≤ 104
- 0 ≤ src, dst, k < n and src ≠ dst
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,000 msC++ 250 msJava 500 msJavaScript 500 msTypeScript 500 ms
Expected complexity
- Time
- O(k * E)
- Space
- O(n)