当前位置：首页 > news >正文

K 站中转内最便宜的航班

news 2025/5/25 5:22:29

题目链接

K 站中转内最便宜的航班

题目描述

注意点

1 <= n <= 100
flights[i].length == 3
0 <= fromi, toi < n
航班没有重复，且不存在自环
k表示经过k个中转，也就是加上起点和终点总共经过k + 2个城市

解答思路

初始想到的是深度优先遍历根据前面的节点找到之后的节点及其路径和，需要注意的是深度不能超过k + 2，但是最终还是超时
参照题解可以使用动态规划完成本题，思路为：arr[i][j]表示正好经过i个城市到达城市j的最低花费，初始只有arr[0][src] = 0，到达其余城市的花费都为最大值INF，随后从src开始，不断更新其所能到达的城市和花费（参照bfs），直到经过了k + 2个城市为止，最终找到arr[i][dst]的最小值就是结果，如果arr[i][dst]的最小值为INF，则结果为-1

代码

class Solution {private final int INF = 10000 * 101 + 1;public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {int res = INF;// arr[i][j]表示正好经过i个城市到达城市j的最低花费int[][] arr = new int[k + 2][n];// 只有arr[0][src]为0，其余为0表示无法到达for (int i = 0; i < k + 2; i++) {Arrays.fill(arr[i], INF);}arr[0][src] = 0;for (int i = 1; i < k + 2; i++) {for (int[] flight : flights) {int prev = flight[0];int next = flight[1];int cost = flight[2];arr[i][next] = Math.min(arr[i][next], arr[i - 1][prev] + cost);}}for (int i = 0; i < k + 2; i++) {res = Math.min(res, arr[i][dst]);}return res == INF ? -1 : res;}
}