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:
![](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png)
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:
![](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-1drawio.png)
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:
![](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-2drawio.png)
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.
不知道怎么判断这样的连通性:
map.get(i[0]).add(new int[]{i[1],i[2]});至少可以这样 用个map存
然后用if(k<0)来退出dfs。
感觉不是特别普遍啊,算了,这道题就这样吧。
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<>()); map.get(i[0]).add(new int[]{i[1],i[2]}); } 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]); } } }标签:src,787,Cheapest,int,dst,Within,dfs,flights,100 From: https://www.cnblogs.com/immiao0319/p/16749893.html