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

链接：787.K站中转内最便宜的航班
难度：Medium
标签：深度优先搜索、广度优先搜索、图、动态规划、最短路、堆（优先队列）
简介：现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k  站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

题解 1 - typescript

• 编辑时间：2021-08-24
• 执行用时：128ms
• 内存消耗：44.6MB
• 编程语言：typescript
• 解法介绍：动态规划，计算每天每个航班的最小值。

function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number
): number {
  const map = new Map<number, number[]>();
  for (let i = 0; i < flights.length; i++) {
    const [from] = flights[i];
    let list = map.get(from);
    if (!list) map.set(from, (list = []));
    list.push(i);
  }
  const dp = new Array(k + 2).fill(0).map(_ => new Array(n).fill(Infinity));
  dp[0][src] = 0;
  let ans = Infinity;
  for (let i = 1; i <= k + 1; i++) {
    for (let j = 0; j < n; j++) {
      if (dp[i - 1][j] === Infinity) continue;
      const list = map.get(j);
      if (!list) continue;
      for (const flightIdx of list) {
        const [, to, price] = flights[flightIdx];
        dp[i][to] = Math.min(dp[i][to], dp[i - 1][j] + price);
        if (to === dst) ans = Math.min(dp[i][to], ans);
      }
    }
  }
  return ans === Infinity ? -1 : ans;
}