题目描述:
有 n 个城市通过一些航班连接。给你一个数组 flights ,其中 flights[i] = [fromi, toi, pricei] ,表示该航班都从城市 fromi 开始,以价格 pricei 抵达 toi。
现在给定所有的城市和航班,以及出发城市 src 和目的地 dst,你的任务是找到出一条最多经过 k 站中转的路线,使得从 src 到 dst 的 价格最便宜 ,并返回该价格。 如果不存在这样的路线,则输出 -1。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
package leetcode; import java.util.ArrayList; import java.util.List; /* Author:Samba Time :2021年8月24日 Data:下午10:17:04 */ //K 站中转内最便宜的航班 public class t787 { public static void main(String[] args) { Solution787 S = new Solution787(); int[][] test = {{3,4,4},{2,5,6},{4,7,10},{9,6,5},{7,4,4},{6,2,10},{6,8,6},{7,9,4},{1,5,4},{1,0,4},{9,7,3},{7,0,5},{6,5,8},{1,7,6},{4,0,9},{5,9,1},{8,7,3},{1,2,6},{4,1,5},{5,2,4},{1,9,1},{7,8,10},{0,4,2},{7,2,8}} ; int result = S.findCheapestPrice(100,test,6, 0, 7); System.out.println(result); } } class Solution787 { private int minResult; private int[][] flights; private int n; private int k; private int dst; //判断是否已经抵达过 public static boolean isArrived(int Node,List<Integer> arrivedNodes) { boolean flag = false; for(int i:arrivedNodes) { if(i==Node) flag = true; } return flag; } //起始地点为s且到达地点没有飞过的数组 public List<int[]> fromS(int s,List<Integer> arrivedNodes) { List<int[]> result = new ArrayList<int[]>(); for(int[] flight:flights) { if(flight[0] == s&&!isArrived(flight[1],arrivedNodes)) { result.add(flight); } } return result; } public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { this.flights = flights; this.n = n; this.k = k; this.dst = dst; this.minResult = Integer.MAX_VALUE; List<Integer> arrivedNodes = new ArrayList<Integer>(); int result = findNext(src,0,0,arrivedNodes); return result==Integer.MAX_VALUE?-1:result; } public int findNext(int src, int value,int time,List<Integer> arrivedNodes) { if(value>=this.minResult) { return Integer.MAX_VALUE; } if(src == dst) { this.minResult = this.minResult>value?value:this.minResult; return value; } if(time>k) { //超过了k条的限制 return Integer.MAX_VALUE; } List<int[]> Next = fromS(src,arrivedNodes); if(Next == null) { //如果最后结果为Integer.MAX_VALUE那么没有一条路走通 return Integer.MAX_VALUE; } List<Integer> tempList = new ArrayList<Integer>(arrivedNodes); tempList.add(src); int result = Integer.MAX_VALUE; for (int[] is : Next) { int tempTime = time + 1; int temp = findNext(is[1],value + is[2],tempTime,tempList); if(temp < result) { result = temp; } } return result; } }
一开始纯BFS,到10个结点就超时了,然后加了不能往回走,17个超时,然后加了到了终点剪枝,100超时,没有再尝试下去了。