本文涉及知识点

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 <= 10⁴
航班没有重复，且不存在自环
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);
		}