Cheapest flight within K stops
MicrosoftThe problem
There are n cities and m edges connected by some number of flights. Given an array of flights where flights[i] = [ fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. Given three integers src, dst, and k, and return the cheapest price from src to dst with at most** k** stops. If there is no such route, return -1.
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 Output: 700 Explanation: The optimal path with at most 1 stops from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 **Explanation:**The optimal path with at most 1 stops from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
Input: n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 0
- 1 <= n <= 100
- 0 <= flights.length <= (n * (n - 1) / 2)
- flights[i].length == 3
- 0 <= fromi, toi < n
- fromi != toi
- 1 <= pricei <= 104
- There will not be any multiple flights between the two cities.
- 0 <= src, dst, k < n
cpp
class Solution{
public:
int CheapestFlight(int n, vector<vector<int>> &flights,
int src, int dst, int K) {
}
};java
class Solution {
public int CheapestFlight(int n, int[][] flights, int src, int dst, int K) {
}
}python
class Solution:
def CheapestFlight(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:javascript
class Solution {
CheapestFlight(n, flights, src, dst, K) {
}
}csharp
class Solution {
public int CheapestFlight(int n, List<List<int>> flights, int src, int dst, int K) {
}
}go
func CheapestFlight(n int, flights [][]int, src int, dst int, K int) int {
}Stuck? Show a way to structure it+
- 01Translate K stops into K+1 edges
- 02Initialize source cost to zero
- 03For each allowed edge count, copy previous costs then relax all flights
- 04Return destination cost or -1
Reference answer
Then expect these follow-ups
How can a priority queue state include remaining stops?
Tests: follow-up reasoning
What if negative costs were allowed?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question