# 787.K 站中转内最便宜的航班 (Medium)

## 问题描述
[787. K 站中转内最便宜的航班 (Medium)](https://leetcode.cn/problems/cheapest-flights-within-k-stops/)

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

现在给定所有的城市和航班，以及出发城市 `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 <= fromᵢ, toᵢ < n`
- `fromᵢ != toᵢ`
- `1 <= priceᵢ <= 10⁴`
- 航班没有重复，且不存在自环
- `0 <= src, dst, k < n`
- `src != dst`

## 解题思路
邻接表存储图，然后使用记忆化搜索。

我们只需要关注当前是第多少个点（不能超过k + 1），假设是第`cnt`个点，那么`dfs(cnt, src) = min(INT_MAX, dfs(cnt + 1, new_src))`，其中`new_src`是以当前点为弧尾的所有点。

## 代码
```cpp
class Solution {
  public:
    const int ubd = 20000000;
    int dfs(int cnt, vector<vector<vector<int>>> &graph, int src, int dst, int k, vector<vector<int>> &cach) {
        if (cnt > k + 1) {
            return ubd;
        }
        if (src == dst) {
            return 0;
        }
        if (cach[cnt][src] >= 0) {
            return cach[cnt][src];
        }
        int res = ubd;
        for (auto &vec : graph[src]) {
            res = std::min(res, vec[1] + dfs(cnt + 1, graph, vec[0], dst, k, cach));
        }
        cach[cnt][src] = res;
        return cach[cnt][src];
    }
    int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int k) {
        vector<vector<vector<int>>> graph(n + 1);
        for (auto &time : flights) {
            graph[time[0]].push_back({time[1], time[2]});
            // graph[time[1]].push_back({time[0], time[2]});
        }
        vector<vector<int>> cach(k + 3, vector<int>(n, -1));
        int res = dfs(0, graph, src, dst, k, cach);
        if (res >= ubd) {
            return -1;
        }
        return res;
    }
};
```