凡科网站建站教程小程序商店

凡科网站建站教程,小程序商店,深圳市建设交易中心网站首页,关键词优化需要从哪些方面开展K 站中转内最便宜的航班 问题描述 有 n 个城市#xff0c;编号从 0 到 n - 1。给你一个航班数组 flights#xff0c;其中 flights[i] [from_i, to_i, price_i] 表示从城市 from_i 到城市 to_i 的航班价格为 price_i。 给你三个整数 src#xff08;出发城市#xff09;、…K 站中转内最便宜的航班问题描述有n个城市编号从0到n - 1。给你一个航班数组flights其中flights[i] [from_i, to_i, price_i]表示从城市from_i到城市to_i的航班价格为price_i。给你三个整数src出发城市、dst目的地城市和k最多中转次数返回从src到dst且最多经过 k 次中转的最便宜价格。如果没有这样的路线返回-1。注意中转次数 航班次数 - 1。例如直接飞行0次中转使用1个航班。示例输入: n 4, flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src 0, dst 3, k 1 输出: 700 解释: 在最多 1 次中转的情况下最便宜的路线是 0-1-3总费用为 100 600 700。算法思路带限制条件的最短路径问题不能直接使用 Dijkstra 算法Dijkstra 无法处理边数限制。核心中转次数最多 k 次中转意味着最多使用 k1 条边动态规划可以按边数或中转次数进行状态转移方法Bellman-Ford 算法天然支持边数限制动态规划dp[stops][city]表示经过 stops 次中转到达 city 的最小费用BFS 剪枝按层数遍历效率低Bellman-Ford 核心思想初始化起点费用为0其他为无穷大迭代 k1 次最多 k1 条边每次迭代中基于上一轮的结果更新当前轮的最短距离使用临时数组避免在同一轮中多次更新代码实现方法一Bellman-Ford 算法importjava.util.*;classSolution{/** * 使用Bellman-Ford算法解K站中转内最便宜的航班 * * param n 城市数量 * param flights 航班信息数组每个元素为[出发城市, 到达城市, 价格] * param src 出发城市 * param dst 目的地城市 * param k 最多中转次数 * return 最便宜价格如果不可达返回-1 */publicintfindCheapestPrice(intn,int[][]flights,intsrc,intdst,intk){// 初始化距离数组dist[i]表示到达城市i的最小费用int[]distnewint[n];Arrays.fill(dist,Integer.MAX_VALUE);dist[src]0;// Bellman-Ford算法最多进行k1轮松弛操作// 最多k次中转所以最多k1条边for(intstops0;stopsk;stops){// 创建临时数组避免在同一轮中使用更新后的值int[]tempDistArrays.copyOf(dist,n);booleanupdatedfalse;// 遍历所有航班for(int[]flight:flights){intfromflight[0];inttoflight[1];intpriceflight[2];// 如果from城市在上一轮中可达尝试更新to城市的费用if(dist[from]!Integer.MAX_VALUE){intnewCostdist[from]price;if(newCosttempDist[to]){tempDist[to]newCost;updatedtrue;}}}// 如果本轮没有更新提前结束if(!updated){break;}// 更新距离数组disttempDist;}// 返回结果returndist[dst]Integer.MAX_VALUE?-1:dist[dst];}}方法二动态规划classSolution{/** * 使用动态规划解K站中转内最便宜的航班 * * param n 城市数量 * param flights 航班信息 * param src 出发城市 * param dst 目的地城市 * param k 最多中转次数 * return 最便宜价格 */publicintfindCheapestPrice(intn,int[][]flights,intsrc,intdst,intk){// dp[i][j] 表示经过最多i次中转到达城市j的最小费用// i的范围是0到k10次中转到k1次中转int[][]dpnewint[k2][n];// 初始化所有费用设为无穷大for(inti0;ik1;i){Arrays.fill(dp[i],Integer.MAX_VALUE);}// 起点费用为00次中转到达起点for(inti0;ik1;i){dp[i][src]0;}// 动态规划填表for(intstops1;stopsk1;stops){// 继承上一轮的结果不使用新的航班for(intcity0;cityn;city){dp[stops][city]dp[stops-1][city];}// 尝试使用所有航班进行更新for(int[]flight:flights){intfromflight[0];inttoflight[1];intpriceflight[2];// 如果from城市在stops-1次中转内可达if(dp[stops-1][from]!Integer.MAX_VALUE){intnewCostdp[stops-1][from]price;dp[stops][to]Math.min(dp[stops][to],newCost);}}}// 返回最多k次中转即k1条边的结果returndp[k1][dst]Integer.MAX_VALUE?-1:dp[k1][dst];}}方法三Dijkstra 变种带状态importjava.util.*;classSolution{/** * 使用Dijkstra算法的变种状态包含(城市, 中转次数) */publicintfindCheapestPrice(intn,int[][]flights,intsrc,intdst,intk){// 构建邻接表Listint[][]graphnewList[n];for(inti0;in;i){graph[i]newArrayList();}for(int[]flight:flights){graph[flight[0]].add(newint[]{flight[1],flight[2]});}// 优先队列[费用, 城市, 中转次数]PriorityQueueint[]pqnewPriorityQueue((a,b)-a[0]-b[0]);pq.offer(newint[]{0,src,0});// 记录到达每个城市在不同中转次数下的最小费用int[][]minCostnewint[n][k2];for(inti0;in;i){Arrays.fill(minCost[i],Integer.MAX_VALUE);}minCost[src][0]0;while(!pq.isEmpty()){int[]currentpq.poll();intcostcurrent[0];intcitycurrent[1];intstopscurrent[2];// 如果到达目的地返回费用if(citydst){returncost;}// 如果中转次数已达到上限不能继续if(stopsk){continue;}// 遍历邻居for(int[]neighbor:graph[city]){intnextCityneighbor[0];intpriceneighbor[1];intnewCostcostprice;intnewStopsstops1;// 如果找到更优的路径if(newCostminCost[nextCity][newStops]){minCost[nextCity][newStops]newCost;pq.offer(newint[]{newCost,nextCity,newStops});}}}return-1;}}算法分析时间复杂度Bellman-FordO(k × E)其中E是航班数量动态规划O(k × E)Dijkstra变种O(E × k × log(V × k))空间复杂度Bellman-FordO(V)动态规划O(V)Dijkstra变种O(V × k)算法过程n 4, flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src 0, dst 3, k 1Bellman-Ford初始化dist [0, ∞, ∞, ∞]第1轮0次中转1条边处理航班[0,1,100]dist[1] min(∞, 0100) 100其他航班的from城市不可达dist [0, 100, ∞, ∞]第2轮1次中转2条边基于第1轮的dist [0, 100, ∞, ∞]处理航班[1,3,600]dist[3] 100 600 700处理航班[1,2,100]dist[2] 100 100 200航班[2,3,200]不能使用因为第1轮中dist[2] ∞所以dist[3] 700测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例int[][]flights1{{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};System.out.println(Test 1: solution.findCheapestPrice(4,flights1,0,3,1));// 700// 测试用例2无法到达int[][]flights2{{0,1,100},{1,2,100}};System.out.println(Test 2: solution.findCheapestPrice(3,flights2,0,2,0));// -1 (需要1次中转但k0)// 测试用例3直接可达int[][]flights3{{0,1,100}};System.out.println(Test 3: solution.findCheapestPrice(2,flights3,0,1,0));// 100// 测试用例4多条路径int[][]flights4{{0,1,100},{0,2,500},{1,2,100}};System.out.println(Test 4: solution.findCheapestPrice(3,flights4,0,2,1));// 200// 测试用例5中转次数为0int[][]flights5{{0,1,100},{1,2,100},{0,2,500}};System.out.println(Test 5: solution.findCheapestPrice(3,flights5,0,2,0));// 500// 测试用例6大价格值int[][]flights6{{0,1,1000000},{1,2,1000000}};System.out.println(Test 6: solution.findCheapestPrice(3,flights6,0,2,1));// 2000000// 测试用例7起点等于终点int[][]flights7{{0,1,100}};System.out.println(Test 7: solution.findCheapestPrice(2,flights7,0,0,0));// 0// 测试用例8复杂的多路径int[][]flights8{{0,1,1},{0,2,5},{1,2,1},{2,3,1}};System.out.println(Test 8: solution.findCheapestPrice(4,flights8,0,3,1));// -1 (需要2次中转)System.out.println(Test 9: solution.findCheapestPrice(4,flights8,0,3,2));// 3 (0-1-2-3)// 测试用例10环路情况int[][]flights10{{0,1,100},{1,2,100},{2,0,100},{1,3,600}};System.out.println(Test 10: solution.findCheapestPrice(4,flights10,0,3,1));// 700}关键点中转次数k次中转 k1条边Bellman-Ford需要执行k1轮临时数组使用临时数组避免在同一轮中多次更新Bellman-Ford算法的核心边界情况处理起点等于终点费用为0无法到达返回-1直接可达1条边0次中转常见问题为什么不能用Dijkstra算法Dijkstra假设一旦找到最短路径就不会被更新这里路径可能更长但中转次数更少需要考虑所有可能性临时数组确保每轮操作只基于上一轮的结果避免在同一轮中使用刚更新的值导致错误的多步更新如何处理负权边Bellman-Ford天然支持负权边