Cheapest flights within k stops
There are n cities numbered 0 to n - 1. Each item of flights is a one-way flight [a, b, price] from city a to city b. You want to get from city src to city dst as cheaply as possible, making at most k stops. A stop is a city where you land and then take another flight, so at most k stops means at most k + 1 flights. The city where the trip starts and the city where it ends are not stops.
Add up the prices of the flights on a trip to get its total. Return the smallest total of any trip that gets from src to dst within the stop limit, or -1 when every trip needs more than k + 1 flights or none reaches dst at all.
n = 4, flights = [[0, 1, 50], [1, 3, 50], [0, 2, 20], [2, 1, 10], [0, 3, 200]], src = 0, dst = 3, k = 1Output1000 to 1 to 3 costs 50 + 50 = 100 with one stop. The cheaper trip 0 to 2 to 1 to 3 (80) makes two stops, so it is not allowed.
n = 4, flights = [[0, 1, 50], [1, 3, 50], [0, 2, 20], [2, 1, 10], [0, 3, 200]], src = 0, dst = 3, k = 2Output80Now two stops are allowed, so 0 to 2 to 1 to 3 costs 20 + 10 + 50 = 80.
n = 3, flights = [[0, 1, 10], [1, 2, 10]], src = 0, dst = 2, k = 0Output-1With no stops you need a direct flight from 0 to 2, and there is none.
2 ≤ n ≤ 100, and 0 ≤ k < n
0 ≤ len(flights) ≤ n · (n - 1)
Every flight is [a, b, price] with 0 ≤ a, b < n, a ≠ b and 1 ≤ price ≤ 104. No two flights share both a and b.
0 ≤ src, dst < n, and src ≠ dst
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.