【C++动态规划 图论】3243. 新增道路查询后的最短距离 I|1567

本文涉及知识点

打开打包代码的方法兼述单元测试

C++动态规划

C++图论

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

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 public: vector vector neiBo[i].emplace_back(i + 1); } vector neiBo[v[0]].emplace_back(v[1]); vector for (const auto& j : neiBo[i]) { dp[j] = min(dp[j] , dp[i] + 1); } } ans.emplace_back(dp.back()); } return ans; } }; 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); } 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); }