787. Cheapest Flights Within K Stops
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
Example 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 graph is shown above.
The optimal path with at most 1 stop 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.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
Example 3:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
Constraints:
1 <= n <= 1000 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= fromi, toi < nfromi != toi1 <= pricei <= 104- There will not be any multiple flights between two cities.
0 <= src, dst, k < nsrc != dst
Solution:
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int result = Integer.MAX_VALUE;
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int[] flight : flights){
int from = flight[0];
int to = flight[1];
int weight = flight[2];
graph.putIfAbsent(from, new ArrayList<>());
graph.get(from).add(new int[]{to, weight});
}
int[] stops = new int[n + 1];
Arrays.fill(stops, Integer.MAX_VALUE);
Set<Integer> visited = new HashSet<>();
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
pq.offer(new int[]{src, 0, 0});
while(!pq.isEmpty()){
int[] cur = pq.poll();
int curNode = cur[0];
int curWeight = cur[1];
int curStops = cur[2];
if (curStops > stops[curNode] || curStops > k + 1){
continue;
}
if (curNode == dst){
return curWeight;
}
stops[curNode] = curStops;
if (visited.contains(curNode)){
continue;
}
if (graph.containsKey(curNode)){
for(int[] nei : graph.get(curNode)){
int nextNode = nei[0];
int nextWeight = nei[1];
pq.offer(new int[]{nextNode, curWeight + nextWeight, curStops + 1});
}
}
}
return -1;
}
}
// TC: O(N∗Log(N))
// SC: O(N)
Dijkstra 解决的问题是：
从 src 出发，找到到每个点的 最短距离（最小 cost）
前提：
- 所有边权非负
- 不关心走了多少步 / 多少中转
- 一旦某个点被“最短距离确定”，就不会再更新
为什么普通 Dijkstra 不适合本题？
本题多了一个约束：
最多 k 个中转站（k+1 条边）
而 Dijkstra 的目标是：
只追求 cost 最小，不关心 stops 数量
这会导致错误结果。
Dijkstra 变形
改造版 Dijkstra（PriorityQueue + BFS）
思路：
- PQ 中存：
(city, cost, stops)- 每次取 cost 最小的
- 如果 city == dst → 返回
- 如果 stops > k → 跳过
- 用二维数组
best[city][stops]防止重复访问
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// Initialize the distance array
int[][] dist = new int[n][k + 2]; // 4, 1+2 =3
/**
0 1 2
0 - - -
1 - - -
2 - - -
3 - - -
*/
// 将数组中的每一行都填充为无穷大 (表示初始时所有城市的最小成本未知)
for (int[] row : dist){
Arrays.fill(row, Integer.MAX_VALUE);
}
dist[src][0] = 0; // start: source city // 设置起点城市src在0次中转的成本为0
/**
0 1 2
0 0 0 -
1 - - -
2 - - -
3 - - -
*/
// Iterate over the number of stops from 0 to k + 1
// because allow k stops, so there will be k+ 1 edge
// 从1次中转开始循环, 到(k+1)次中转为止
for (int stops = 1; stops <= k + 1; stops++){
// 在每一轮中转开始时, 将上一轮的成本拷贝到当前轮次
for (int i = 0; i < n; i++){
dist[i][stops] = dist[i][stops - 1];
// dist[0][1] = dist[0][0] = 0
// dist[1][1] = dist[1][0] = -
}
// 遍历所有的航班信息
for (int[] flight : flights){
// [0, 1, 100]
int from = flight[0];//0
int to = flight[1];//1
int price = flight[2]; // 100
if (dist[from][stops - 1] != Integer.MAX_VALUE){
// dist[0][0] = 0
dist[to][stops] = Math.min(dist[to][stops], dist[from][stops - 1] + price);
// dist[1][1] = Math.min(dist[1][1], dist[0][1] + 100);
// dist[1][1] = Math.min(-, 100)
// dist[1][1] = 100
}
}
}
// Find the minimum cost to reach dst with up to k + 1 stops
int minCost = Integer.MAX_VALUE;
for (int stops = 0; stops <= k + 1; stops++){
minCost = Math.min(minCost, dist[dst][stops]);
}
return minCost == Integer.MAX_VALUE ? -1 : minCost;
}
}
int[][] dist = new int[n][k + 2];n: 数组的行数等于城市的数量, 每一行代表一个城市
k+2: 需要考虑从0次中转到k+1次中转的情况
Bellman Ford
The “Dijkstra algorithm” is restricted to solving the “single source shortest path” problem in graphs without negative weights.
How could we solve the “single source shortest path” problem in graphs with negative weights?
Bellman-Ford algorithm.
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE/2;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;
for (int i = 0; i <= k; i++){
int[] temp = Arrays.copyOf(dist, n);
for (int[] f : flights){
int u = f[0];
int v = f[1];
int w = f[2];
if (dist[u] != INF){
temp[v] = Math.min(temp[v], dist[u] + w);
}
}
dist = temp;
}
return dist[dst] == INF ? -1 : dist[dst];
}
}
// TC: O(K*flights.length);
// SC: O(n)
https://www.youtube.com/watch?v=FtN3BYH2Zes
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE / 2;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;
for (int i = 0; i <= k; i++){// k
int[] temp = new int[n];
for (int j = 0; j < n; j++){// n
temp[j] = dist[j];
}
for (int[] f : flights){ // f
int from = f[0];
int to = f[1];
int price = f[2];
if (dist[from] != INF){
temp[to] = Math.min(temp[to], dist[from] + price);
}
}
dist = temp;
}
if (dist[dst] == INF){
return -1;
}else{
return dist[dst];
}
}
}
// TC: O(K*flights.length);
// SC: O(n)