LeetCode: 787. K 站中转内最便宜的航班

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

787. K 站中转内最便宜的航班

有 n 个城市通过一些航班连接。给你一个数组 flights，其中 flights[i] = [from_i, to_i, price_i]，表示该航班都从城市 `from_i 开始，以价格 `price_i 抵达 `to_i。

现在给定所有的城市和航班，以及出发城市 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 <= from_i, to_i < n
from_i != to_i
1 <= price_i <= 10⁴
航班没有重复，且不存在自环
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;
}

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * 暴力破解（32/58，报错）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-19 21:36:05
 */
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
  Map<Integer, List<int[]>> srcToDst = new HashMap<>(n);
  Map<Integer, List<int[]>> dstToSrc = new HashMap<>(n);
  for (int[] flight : flights) {
    int s = flight[0];
    int d = flight[1];
    int p = flight[2];
    srcToDst.computeIfAbsent(s, _ -> new ArrayList<>(n)).add(new int[]{d, p});
    dstToSrc.computeIfAbsent(d, _ -> new ArrayList<>(n)).add(new int[]{s, p});
  }
  // 题目理解错了：最多经过 k 站中转
  Map<Integer, Integer> prices = dfs(srcToDst, dstToSrc, src, Set.of(dst), k + 1);
  return prices.isEmpty() ? -1 : prices.values().stream().min(Integer::compareTo).get();
}

private Map<Integer, Integer> dfs(Map<Integer, List<int[]>> srcToDst,
                                  Map<Integer, List<int[]>> dstToSrc,
                                  int src, Set<Integer> dsts, int k) {
  if (k == 1) {
    List<int[]> ints = srcToDst.getOrDefault(src, Collections.emptyList());
    Map<Integer, Integer> result = new HashMap<>();
    for (int[] anInt : ints) {
      int d = anInt[0];
      if (dsts.contains(d)) {
        result.put(d, anInt[1]);
      }
    }
    return result;
  }
  List<int[]> preSrcs = new ArrayList<>();
  for (Integer dst : dsts) {
    preSrcs.addAll(dstToSrc.getOrDefault(dst, Collections.emptyList()));
  }
  Set<Integer> preDsts = preSrcs.stream()
    .map(a -> a[0]).collect(Collectors.toSet());
  if (preDsts.isEmpty()) {
    return Collections.emptyMap();
  }
  Map<Integer, Integer> preResult = dfs(srcToDst, dstToSrc, src, preDsts, k - 1);
  if (preResult.isEmpty()) {
    return Collections.emptyMap();
  }
  Map<Integer, Integer> result = new HashMap<>();
  for (Map.Entry<Integer, Integer> entry : preResult.entrySet()) {
    Integer ps = entry.getKey();
    Integer pp = entry.getValue();
    List<int[]> next = srcToDst.getOrDefault(ps, Collections.emptyList());
    for (int[] ints : next) {
      int d = ints[0];
      if (dsts.contains(d)) {
        result.put(d, pp + ints[1]);
      }
    }
  }
  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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-19 21:36:05
 */
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
  final int MAX = 10000 * 101 + 1;
  int[][] dp = new int[k + 2][n];
  for (int[] ints : dp) {
    Arrays.fill(ints, MAX);
  }
  dp[0][src] = 0;
  for (int i = 1; i <= k + 1; i++) {
    for (int[] flight : flights) {
      int s = flight[0], d = flight[1], c = flight[2];
      dp[i][d] = Math.min(dp[i][d], dp[i - 1][s] + c);
    }
  }
  int result = MAX;
  for (int i = 1; i <= k + 1; i++) {
    result = Math.min(result, dp[i][dst]);
  }
  return result == MAX ? -1 : result;
}

LeetCode: 787. K 站中转内最便宜的航班

友情支持

787. K 站中转内最便宜的航班

思路分析

参考资料