Back to DSA
Cheapest Flights Within K Stops
hardA network of n cities is connected by directed flights, each with an associated cost. Given a starting city, a destination city, and a limit of at most k intermediate stops, find the lowest-cost route. If no valid route exists within the stop constraint, return -1.
Examples
Example 1:
Input:
n = 3, flights = [[0,1,200],[1,2,200],[0,2,500]], src = 0, dst = 2, k = 1Output:
400Explanation: Route 0->1->2 costs 400 with 1 stop, cheaper than the direct flight at 500.
Example 2:
Input:
n = 3, flights = [[0,1,200],[1,2,200],[0,2,500]], src = 0, dst = 2, k = 0Output:
500Explanation: With zero intermediate stops, only the direct flight 0->2 at cost 500 qualifies.
Hints
import java.util.*;
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[] prices = new int[n];
Arrays.fill(prices, Integer.MAX_VALUE);
prices[src] = 0;
for (int i = 0; i <= k; i++) {
int[] temp = Arrays.copyOf(prices, n);
for (int[] f : flights) {
if (prices[f[0]] != Integer.MAX_VALUE) {
temp[f[1]] = Math.min(temp[f[1]], prices[f[0]] + f[2]);
}
}
prices = temp;
}
return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
}
}Time complexity
O(k * E)Space complexity
O(V)