友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
787. K 站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights，其中 flights[i] = [fromi, toi, pricei]，表示该航班都从城市 `fromi 开始，以价格 `pricei 抵达 `toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
示例 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 解释: 城市航班图如上 从城市 0 到城市 3 经过最多 1 站的最佳路径用红色标记，费用为 100 + 600 = 700。 请注意，通过城市 [0, 1, 2, 3] 的路径更便宜，但无效，因为它经过了 2 站。
示例 2：
输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 输出: 200 解释: 城市航班图如上 从城市 0 到城市 2 经过最多 1 站的最佳路径标记为红色，费用为 100 + 100 = 200。
示例 3：
输入：n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 输出：500 解释： 城市航班图如上 从城市 0 到城市 2 不经过站点的最佳路径标记为红色，费用为 500。
提示：
-
1 <= n <= 100 -
0 <= flights.length <= (n * (n - 1) / 2) -
flights[i].length == 3 -
0 <= fromi, toi < n -
fromi != toi -
1 <= pricei <= 104 -
航班没有重复，且不存在自环
-
0 <= src, dst, k < n -
src != dst
思路分析
-
一刷（深度优先搜索，超时）
-
一刷（带备忘录的深度优先搜索）
-
一刷（动态规划）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* 通过 48 / 56 个测试用例。然后超时
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-06 18:53:25
*/
int result = Integer.MAX_VALUE;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Map<Integer, List<int[]>> srcMap = new HashMap<>();
for (int[] flight : flights) {
int start = flight[0];
srcMap.computeIfAbsent(start, x -> new ArrayList<>()).add(flight);
}
dfs(n, srcMap, src, dst, k + 1, 0);
return result == Integer.MAX_VALUE ? -1 : result;
}
private void dfs(int n, Map<Integer, List<int[]>> srcMap,
int src, int dst, int k, int expend) {
if (k < 0) {
return;
}
if (src == dst) {
result = Math.min(result, expend);
return;
}
for (int[] flight : srcMap.getOrDefault(src, Collections.emptyList())) {
int idst = flight[1];
int cost = flight[2];
// 不加该判断，通过 28 / 56 个测试用例；加上，通过 48 / 56 个测试用例
if (cost + expend >= result) {
continue;
}
dfs(n, srcMap, idst, dst, k - 1, cost + expend);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-06 21:30:38
*/
final int MAX = 100 * 10000 + 1;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Map<Integer, List<int[]>> srcMap = new HashMap<>();
for (int[] flight : flights) {
int start = flight[0];
srcMap.computeIfAbsent(start, x -> new ArrayList<>()).add(flight);
}
int[][] memo = new int[n][k + 1];
int result = dfs(n, srcMap, src, dst, k + 1, memo);
return result == MAX ? -1 : result;
}
private int dfs(int n, Map<Integer, List<int[]>> srcMap,
int src, int dst, int k, int[][] memo) {
if (k < 0) {
return MAX;
}
if (src == dst) {
return 0;
}
if (memo[src][k] != 0) {
return memo[src][k];
}
int result = MAX;
for (int[] flight : srcMap.getOrDefault(src, Collections.emptyList())) {
int idst = flight[1];
int cost = flight[2];
result = Math.min(result, dfs(n, srcMap, idst, dst, k - 1, memo) + cost);
}
memo[src][k] = result;
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-05-06 21:40:38
*/
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
final int MAX = 100 * 10000 + 1;
int[][] dp = new int[k + 2][n];
for (int i = 0; i < k + 2; i++) {
Arrays.fill(dp[i], MAX);
}
dp[0][src] = 0;
for (int i = 1; i < k + 2; i++) {
for (int[] flight : flights) {
int start = flight[0];
int end = flight[1];
int cost = flight[2];
dp[i][end] = Math.min(dp[i][end], dp[i - 1][start] + cost);
}
}
int result = MAX;
for (int i = 1; i < k + 2; i++) {
result = Math.min(result, dp[i][dst]);
}
return result == MAX ? -1 : result;
}