Cheapest Flight With a Limited Number of Layovers
Implement cheapestWithStops
You are given the flights between n airports as a price matrix (0 means there is no flight). Find the cheapest way to fly from a source to a destination using at most k layovers, i.e. at most k + 1 flights, or -1 if that is impossible.
The cheapest route overall may use too many flights, so ordinary shortest-path search is not enough: the number of flights must be part of the state. Running Bellman-Ford for exactly k + 1 rounds does that.
Example 1:
Input: prices = [[0,5,12,9,0],[0,0,4,0,0],[0,0,0,0,3],[0,0,0,0,5],[0,0,0,0,0]], src = 0, dst = 4, k = 1
Output: 14
Example 2:
Input: prices = [[0,5,12,9,0],[0,0,4,0,0],[0,0,0,0,3],[0,0,0,0,5],[0,0,0,0,0]], src = 0, dst = 4, k = 2
Output: 12
Example 3:
Input: prices = [[0,5],[0,0]], src = 1, dst = 0, k = 3
Output: -1
+ 16 hidden test cases run on Submit.
Constraints:
- ●
2 ≤ n ≤ 8 airports numbered 0 … n-1; prices is an n × n matrix: prices[u][v] = 0 means no flight from u to v, prices[u][v] = p (1 ≤ p ≤ 30) means a one-way flight costing p - ●
0 ≤ src, dst < n and src ≠ dst; 0 ≤ k ≤ 6 is the largest allowed number of layovers (airports visited strictly between src and dst) - ●
A route with at most k layovers therefore uses at most k + 1 flights - ●
Return the cheapest total price of such a route, or -1 if there is none
prices =
src =
dst =
k =