本文涉及知识点

打开打包代码的方法兼述单元测试
C++动态规划
C++图论

LeetCode3243. 新增道路查询后的最短距离 I

给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。
queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。
示例 1：
输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出： [3, 2, 1]
解释：
新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。
新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。
新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。
示例 2：
输入： n = 4, queries = [[0, 3], [0, 2]]
输出： [1, 1]
解释：
新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。
提示：
3 <= n <= 500
1 <= queries.length <= 500
queries[i].length == 2
0 <= queries[i][0] < queries[i][1] < n
1 < queries[i][1] - queries[i][0]
查询中没有重复的道路。

图论 最短路

注意： 无论是初始路线，还是新增加的路线，都是终点>起点。$\to$ 经过的城市一定是升序。

动态规划的状态表示

dp[i]表示到达i的最少路径。空间复杂度：O(n)

动态规划的填表顺序

令新增加的边是i1->i2。
则 i = i2 ; i > N; i++

动态规划的转移方程

MinSelf(dp[i2],dp[i1]+1)
for(next in neiBo[i])
MinSelf(dp[next],dp[i]+1)
新增一条的时间复杂度：O(m），m是边数，本题是n+q。
总时间复杂度：O(q(n+q))

动态规划的初始化

dp[0]=0，其它INT_MAX/2。
先计算初始各边，再增加查询各边。
增加完边后，刷新dp[i…]封装成函数。也可以进一步简化，更新整个dp。

动态规划的返回值

dp.back

代码

核心代码

class Solution {
		public:
			vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
				vector<vector<int>> neiBo(n);
				for (int i = 0; i + 1 < n; i++) {
					neiBo[i].emplace_back(i + 1);
				}
				vector<int> ans;
				for (const auto& v : queries) {
					neiBo[v[0]].emplace_back(v[1]);
					vector<int> dp(n, INT_MAX / 2);
					dp[0] = 0;
					for (int i = 0; i < n; i++) {
						for (const auto& j : neiBo[i]) {
							dp[j] = min(dp[j] , dp[i] + 1);
						}
					}
					ans.emplace_back(dp.back());
				}
				return ans;
			}
		};

代码

核心代码

int n;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{
			n = 5, queries = { {2, 4}, {0, 2}, {0, 4} };
			auto res = Solution().shortestDistanceAfterQueries(n, queries);
			AssertEx({ 3,2,1 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 4, queries = { {0, 3}, {0, 2} };
			auto res = Solution().shortestDistanceAfterQueries(n, queries);
			AssertEx({ 1,1 }, res);
		}

单元测试

int n;
		vector<vector<int>> queries;
		TEST_METHOD(TestMethod11)
		{
			n = 5, queries = { {2, 4}, {0, 2}, {0, 4} };
			auto res = Solution().shortestDistanceAfterQueries(n, queries);
			AssertEx({ 3,2,1 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 4, queries = { {0, 3}, {0, 2} };
			auto res = Solution().shortestDistanceAfterQueries(n, queries);
			AssertEx({ 1,1 }, res);
		}