• 欢迎光临~

# 787. Cheapest Flights Within K Stops 无坐标图，能停k站，最便宜的飞机

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.
```

```class Solution {
int ans_dfs;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K)
{
ans_dfs=Integer.MAX_VALUE;
Map<Integer,List<int[]>> map=new HashMap<>();
for(int[] i:flights)
{
map.putIfAbsent(i[0],new ArrayList<>());
}
dfs(map,src,dst,K+1,0);
return ans_dfs==Integer.MAX_VALUE?-1:ans_dfs;
}
public void dfs(Map<Integer,List<int[]>> map, int src, int dst, int k, int cost)
{
if(k<0)
return;
if(src==dst)
{
ans_dfs=cost;
return;
}
if(!map.containsKey(src))
return;
for(int[] i:map.get(src))
{
if(cost+i[1]>ans_dfs)               //Pruning, check the sum of current price and next cost. If it's greater then the ans so far, continue
continue;
dfs(map,i[0],dst,k-1,cost+i[1]);
}
}
}```