Given n cities connected by flights with cost, find the cheapest price from src to dst with at most k stops. Return -1 if impossible.
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: 700Input: n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1 → Output: 200
Bellman-Ford with at most k+1 relaxations. Use a temporary array to avoid using edges from the current round.
- Initialize prices[] with INF, prices[src]=0.
- Repeat k+1 times: copy prices to temp; for each flight [u,v,cost]: if prices[u]+cost < temp[v]: temp[v]=prices[u]+cost.
- Set prices = temp.
- Return prices[dst] or -1 if INF.
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 = prices.clone();
for (int[] f : flights) {
if (prices[f[0]] != Integer.MAX_VALUE && prices[f[0]] + f[2] < temp[f[1]])
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(N)