Every day a Leetcode

题目来源：3243. 新增道路查询后的最短距离 I

解法1：广度优先搜索

暴力。

每次加边后重新跑一遍 BFS，求出从 0 到 n−1 的最短路。

代码：

/** @lc app=leetcode.cn id=3243 lang=cpp** [3243] 新增道路查询后的最短距离 I*/// @lc code=start// 广度优先搜索class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries){vector<int> e[n];// 建图for (int i = 1; i < n; i++)e[i - 1].push_back(i);auto bfs = [&](){int dis[n];memset(dis, -1, sizeof(dis));queue<int> q;q.push(0);dis[0] = 0;while (!q.empty()){int sn = q.front();q.pop();for (int fn : e[sn])if (dis[fn] == -1){q.push(fn);dis[fn] = dis[sn] + 1;}}return dis[n - 1];};vector<int> ans;for (vector<int> &q : queries){e[q[0]].push_back(q[1]);int res = bfs();ans.push_back(res);}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(q(n+q))，其中 q 是数组 queries 的长度。每次 BFS 的时间是 O(n+q)。

空间复杂度：O(n+q)，其中 q 是数组 queries 的长度。

解法2：动态规划

定义 dp[i] 为从 0 到 i 的最短路。

用 from[i] 记录额外添加的边的终点是 i，起点列表是 from[i]。

我们可以从 i−1 到 i，也可以从 from[i][j] 到 i，这些位置作为转移来源，用其 dp 值 +1 更新 dp[i] 的最小值。

初始值：dp[i]=i。

答案：dp[n−1]。

注意：设添加的边为 l→r，只有当 dp[l]+1<dp[r] 时才更新 DP。

代码：

/** @lc app=leetcode.cn id=3243 lang=cpp** [3243] 新增道路查询后的最短距离 I*/// @lc code=start// 动态规划class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries){vector<int> dp(n);vector<vector<int>> from(n);// 初始化：dp[i] = iiota(dp.begin(), dp.end(), 0);vector<int> ans;// 状态转移for (vector<int> &q : queries){int l = q[0], r = q[1];from[r].push_back(l);if (dp[l] + 1 < dp[r]){dp[r] = dp[l] + 1;// 更新后面的最短路for (int i = r + 1; i < n; i++){dp[i] = min(dp[i], dp[i - 1] + 1);for (int j : from[i]){// 存在一条 j->i 的路径dp[i] = min(dp[i], dp[j] + 1);}}}ans.push_back(dp[n-1]);}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(q(n+q))，其中 q 是数组 queries 的长度。

空间复杂度：O(n+q)，其中 q 是数组 queries 的长度。