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

题目链接

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

分析

简单的做法就是直接进行 BFS 求解，可以使用 DP 进行优化

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

用 $pre[i]$ 记录终点为 $i$ 的额外添加的边的起点表

那么，对于每个点，可以从 $i - 1$ 到 $i$ ，或是从 $pre[i]$ 中的任意一点到 $i$

于是我们用这些点作为转移来源，更新 $dp[i]$ 的最小值

答案即为 $dp[n - 1]$

代码实现

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        int m = queries.size();
        vector<int> ans, dp(n);
        vector<vector<int>> pre(n);
        for(int i = 1; i < n; ++i)
            dp[i] = i, pre[i].emplace_back(i - 1);

        for(auto &query : queries)
        {
            pre[query[1]].emplace_back(query[0]);
            for(int v = query[1]; v < n; ++v)
                for(int u : pre[v])
                    dp[v] = min(dp[v], dp[u] + 1);
            ans.emplace_back(*dp.rbegin());
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(q * (n + q))$ ，$q$ 为 $query$ 的长度
• 空间复杂度：$O(n+q)$