Question

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

English Version

题目描述

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

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

 

示例 1：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下


从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下


从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 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

解法

方法一：Bellman Ford 算法

class Solution:
  def findCheapestPrice(
    self, n: int, flights: List[List[int]], src: int, dst: int, k: int
  ) -> int:
    INF = 0x3F3F3F3F
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):
      backup = dist.copy()
      for f, t, p in flights:
        dist[t] = min(dist[t], backup[f] + p)
    return -1 if dist[dst] == INF else dist[dst]

class Solution {
  private static final int INF = 0x3f3f3f3f;

  public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    int[] backup = new int[n];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    for (int i = 0; i < k + 1; ++i) {
      System.arraycopy(dist, 0, backup, 0, n);
      for (int[] e : flights) {
        int f = e[0], t = e[1], p = e[2];
        dist[t] = Math.min(dist[t], backup[f] + p);
      }
    }
    return dist[dst] == INF ? -1 : dist[dst];
  }
}

class Solution {
public:
  int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    const int inf = 0x3f3f3f3f;
    vector<int> dist(n, inf);
    vector<int> backup;
    dist[src] = 0;
    for (int i = 0; i < k + 1; ++i) {
      backup = dist;
      for (auto& e : flights) {
        int f = e[0], t = e[1], p = e[2];
        dist[t] = min(dist[t], backup[f] + p);
      }
    }
    return dist[dst] == inf ? -1 : dist[dst];
  }
};

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
  const inf = 0x3f3f3f3f
  dist := make([]int, n)
  backup := make([]int, n)
  for i := range dist {
    dist[i] = inf
  }
  dist[src] = 0
  for i := 0; i < k+1; i++ {
    copy(backup, dist)
    for _, e := range flights {
      f, t, p := e[0], e[1], e[2]
      dist[t] = min(dist[t], backup[f]+p)
    }
  }
  if dist[dst] == inf {
    return -1
  }
  return dist[dst]
}

方法二：DFS + 记忆化搜索

class Solution:
  def findCheapestPrice(
    self, n: int, flights: List[List[int]], src: int, dst: int, k: int
  ) -> int:
    @cache
    def dfs(u, k):
      if u == dst:
        return 0
      if k <= 0:
        return inf
      k -= 1
      ans = inf
      for v, p in g[u]:
        ans = min(ans, dfs(v, k) + p)
      return ans

    g = defaultdict(list)
    for u, v, p in flights:
      g[u].append((v, p))
    ans = dfs(src, k + 1)
    return -1 if ans >= inf else ans

class Solution {
  private int[][] memo;
  private int[][] g;
  private int dst;
  private static final int INF = (int) 1e6;

  public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    n += 10;
    memo = new int[n][n];
    for (int i = 0; i < n; ++i) {
      Arrays.fill(memo[i], -1);
    }
    g = new int[n][n];
    for (int[] e : flights) {
      g[e[0]][e[1]] = e[2];
    }
    this.dst = dst;
    int ans = dfs(src, k + 1);
    return ans >= INF ? -1 : ans;
  }

  private int dfs(int u, int k) {
    if (memo[u][k] != -1) {
      return memo[u][k];
    }
    if (u == dst) {
      return 0;
    }
    if (k <= 0) {
      return INF;
    }
    int ans = INF;
    for (int v = 0; v < g[u].length; ++v) {
      if (g[u][v] > 0) {
        ans = Math.min(ans, dfs(v, k - 1) + g[u][v]);
      }
    }
    memo[u][k] = ans;
    return ans;
  }
}

class Solution {
public:
  vector<vector<int>> memo;
  vector<vector<int>> g;
  int dst;
  int inf = 1e6;

  int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
    n += 10;
    memo.resize(n, vector<int>(n, -1));
    g.resize(n, vector<int>(n));
    for (auto& e : flights) g[e[0]][e[1]] = e[2];
    this->dst = dst;
    int ans = dfs(src, k + 1);
    return ans >= inf ? -1 : ans;
  }

  int dfs(int u, int k) {
    if (memo[u][k] != -1) return memo[u][k];
    if (u == dst) return 0;
    if (k <= 0) return inf;
    int ans = inf;
    for (int v = 0; v < g[u].size(); ++v)
      if (g[u][v] > 0)
        ans = min(ans, dfs(v, k - 1) + g[u][v]);
    memo[u][k] = ans;
    return memo[u][k];
  }
};

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
  n += 10
  memo := make([][]int, n)
  g := make([][]int, n)
  for i := range memo {
    memo[i] = make([]int, n)
    g[i] = make([]int, n)
    for j := range memo[i] {
      memo[i][j] = -1
    }
  }

  for _, e := range flights {
    g[e[0]][e[1]] = e[2]
  }
  inf := int(1e6)
  var dfs func(u, k int) int
  dfs = func(u, k int) int {
    if memo[u][k] != -1 {
      return memo[u][k]
    }
    if u == dst {
      return 0
    }
    if k <= 0 {
      return inf
    }
    ans := inf
    for v, p := range g[u] {
      if p > 0 {
        ans = min(ans, dfs(v, k-1)+p)
      }
    }
    memo[u][k] = ans
    return ans
  }
  ans := dfs(src, k+1)
  if ans >= inf {
    return -1
  }
  return ans
}