问题描述 链接到标题

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

有 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是以当前点为弧尾的所有点。

代码 链接到标题 

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;
    }
};