Back to course home
0% completed
Vote For New Content
Cheapest Flights Within K Stops (medium)
Problem Statement
There are n cities connected by flights. You are given an array flights where flights[i] = [from<sub>i</sub>, to<sub>i</sub>, price<sub>i</sub>] indicates that there is a flight from city from<sub>i</sub> to city to<sub>i</sub> with cost price<sub>i</sub>.
Find the cheapest flight price a src city to a dst city, but you are allowed to have at most k stops. If there is no such route, return -1.
Examples
Example 1:
- Input:
n = 5, flights =[[0, 1, 50], [1, 2, 50], [2, 3, 50], [3, 4, 50], [0, 4, 300]], src =1, dst =4, k =2 - Expected Output:
150
- Explanation: The cheapest flight route from city 1 to city 4 with at most 2 stops is 1 -> 2 -> 3 -> 4. The total cost is 50 + 50 + 50 = 150.
Example 2:
- Input:
n = 4, flights =[[0, 1, 100], [1, 2, 200], [2, 3, 300], [0, 3, 500]], src =0, dst =3, k =1 - Expected Output:
500
- Explanation: The cheapest flight route from city 0 to city 3 with at most 1 stop is 0 -> 3. The total cost is 500.
Example 3:
- Input: n =
3, flights =[[0, 1, 100], [1, 2, 100], [0, 2, 500]], src =0, dst =2, k =1 - Expected Output:
200
- Explanation: The cheapest flight route from city 0 to city 2 with at most 1 stop is 0 -> 1 -> 2. The total cost is 100 + 100 = 200.
Constraints:
- 1 <= n <= 100
- 0 <= flights.length <= (n * (n - 1) / 2)
- flights[i].length == 3
- 0 <= from<sub>i</sub>, to<sub>i</sub> < n
- from<sub>i</sub> != to<sub>i</sub>
- 1 <= price<sub>i</sub> <= 104
- There will not be any multiple flights between two cities.
- 0 <= src, dst, k < n
- src != dst
Python3
Python3
. . . .
.....
.....
.....
Like the course? Get enrolled and start learning!
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible