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
Hiring now
Get the Microsoft interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question