题目描述
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
Example 1:
输入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 输出: 200 解释: 城市航班图如下
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
Example 2:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 输出: 500 解释: 城市航班图如下
Constraints:
- 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
解题思路
- 用dp[t][i] // 从出发城市src到达城市i所需要的最小花费
- 状态转移方程为，dp[t][i] = min(dp[t][i], dp[t - 1][j] + cost[j][i])(枚举最后一次航班的起点j，前t-1次航班的最小花费为dp[t - 1][j]加上由j -> i的花费的最小值)
- 由于经过k次中转，最多可以乘k + 1次航班，下标从1开始的话，申请空间时就应该是k + 2
- 最终答案为，min(f[1][dst], f[2][dst], …, f[k + 1][dst])
- 根据题目所给的数据，航班花费不超过10^4,最多达成航班的次数k + 1不超过101，极大值设为这两者的乘积即可
C++代码
class Solution {
private:
static constexpr int INF = 10000 * 101 + 1;
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<int>> f(k + 2, vector<int>(n, INF));
f[0][src] = 0;
for(int t = 1; t <= k + 1; t++){
for(auto&& flight : flights){
int from = flight[0], to = flight[1], cost = flight[2];
f[t][to] = min(f[t][to], f[t - 1][from] + cost);
}
}
int ans = INF;
for(int t = 1; t <= k + 1; t++){
ans = min(ans, f[t][dst]);
}
return ans == INF ? -1 : ans;
}
};
