本文涉及知识点
C++动态规划
C++图论
LeetCode787. K 站中转内最便宜的航班
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
示例 1：
输入:
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
输出: 700 解释: 城市航班图如上
从城市 0 到城市 3 经过最多 1 站的最佳路径用红色标记，费用为 100 + 600 = 700。
请注意，通过城市 [0, 1, 2, 3] 的路径更便宜，但无效，因为它经过了 2 站。
示例 2：
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如上
从城市 0 到城市 2 经过最多 1 站的最佳路径标记为红色，费用为 100 + 100 = 200。
示例 3：
输入：n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
输出：500
解释：
城市航班图如上
从城市 0 到城市 2 不经过站点的最佳路径标记为红色，费用为 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
动态规划
动态规划的状态表示
dp[i][dest]：记录除起点外，经过i个站点到达dest需要的最少费用。值为INT_MIN/2 表示不存在的路径。
pre=dp[i],cur = dp[i+1]
空间复杂度：用滚动向量，O(n)
动态规划的转移方程
For j = 0 To n-1
for(const auto& [next,price] : flights[j]){
dp[next] = min(dp[next],pre[j]+price);
}
每个状态的转移方程时间复杂度是：O(n)
总时间复杂度是：O(knn)。
动态规划的初始值
pre[src] = 0，其它不存在。
动态规划的填表顺序
i = 0 To k+1
动态规划的返回值
所有pre[dest]的最小值。如果大于等于INT_MIN/2，返回-1。
代码
核心代码
class CNeiBo
{
public:
static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
if (!bDirect)
{
vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
if (!bDirect)
{
vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
}
}
return vNeiBo;
}
static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
{
vector<vector<int>> neiBo(neiBoMat.size());
for (int i = 0; i < neiBoMat.size(); i++)
{
for (int j = i + 1; j < neiBoMat.size(); j++)
{
if (neiBoMat[i][j])
{
neiBo[i].emplace_back(j);
neiBo[j].emplace_back(i);
}
}
}
return neiBo;
}
};
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
int iMin = INT_MAX / 2;
vector<int> pre(n, INT_MAX / 2);
pre[src] = 0;
auto neiBo = CNeiBo::Three(n, flights, true, 0);
for (int i = 0; i <= k; i++) {
vector<int> dp(n, INT_MAX / 2);
for (int j = 0; j < n; j++) {
for (const auto& [next, price] : neiBo[j]) {
dp[next] = min(dp[next], pre[j] + price);
}
}
pre.swap(dp);
iMin = min(iMin, pre[dst]);
}
return iMin >= INT_MAX/2 ? -1 : iMin;
}
};
单元测试
int n, src, dst, k;
vector<vector<int>> edges;
TEST_METHOD(TestMethod11)
{
n = 4, edges = { {0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200} }, src = 0, dst = 3, k = 1;
auto res = Solution().findCheapestPrice(n, edges, src, dst, k);
AssertEx(700, res);
}
TEST_METHOD(TestMethod12)
{
n = 3, edges = { {0,1,100},{1,2,100},{0,2,500} }, src = 0, dst = 2, k = 1;
auto res = Solution().findCheapestPrice(n, edges, src, dst, k);
AssertEx(200, res);
}
TEST_METHOD(TestMethod13)
{
n = 3, edges = { {0,1,100},{1,2,100},{0,2,500} }, src = 0, dst = 2, k = 0;
auto res = Solution().findCheapestPrice(n, edges, src, dst, k);
AssertEx(500, res);
}
TEST_METHOD(TestMethod14)
{
n = 5, edges = { {1,2,10},{2,0,7},{1,3,8},{4,0,10},{3,4,2},{4,2,10},{0,3,3},{3,1,6},{2,4,5} }, src = 0, dst = 4, k = 1;
auto res = Solution().findCheapestPrice(n, edges, src, dst, k);
AssertEx(5, res);
}
