LeetCode 3243. Shortest Distance After Road Addition Queries I

🔗 https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i

题目

• 有 n 个城市，编号 0 ~ n-1，从城市 i 到 i+1 有一条路
• 给若干高速路，表明从城市 u 到 v 有一条新增的路，v - u > 1
• 返回每新增一条高速路的情况下，城市 0 到城市 n-1 的最短路径条数

思路

• 初始化二维数组表明城市 i j 的路径条数
• 朴素思路，每新增一条路径，算一遍 Dijkstra，TLE
• 优化思路，新增了路径 u → v，那么 u 之前的城市 i（含u）到 v 的路径都可以松弛优化，对应着 i 到 v 之后的城市也都可以优化
• 其他思路，用邻接表存储边关系，BFS 找到最短路径

代码

class Solution {
public:vector<int> shortestDistanceAfterQueries(int n,vector<vector<int>>& queries) {vector<vector<int>> m(n, vector<int>(n));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {m[i][j] = -1;if (j > i) m[i][j] = j - i;}m[i][i] = 0;}vector<int> ans;for (auto& query : queries) {int u = query[0], v = query[1];m[u][v] = 1;for (int i = 0; i <= u; i++) {m[i][v] = min(m[i][v], m[i][u] + m[u][v]);for (int j = v; j < n; j++) {m[i][j] = min(m[i][j], m[i][v] + m[v][j]);}}ans.push_back(m[0][n - 1]);}return ans;}
};