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

【LetMeFly】3243.新增道路查询后的最短距离 I：动态规划(DP)

力扣题目链接：https://leetcode.cn/problems/shortest-distance-after-road-addition-queries-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]
• 查询中没有重复的道路。

解题方法：动态规划

这道题有点意思，只有小编号城市指向大编号城市这一说。

因此我们可以使用：dp数组，dp[i]代表0到i的最短距离；fromList数组，fromList[i]代表所有能通向i的节点。

每次新增一条边（假设从from到to），就从to开始遍历到n - 1。对于遍历到的节点i，$dp[i]=\min dp[i], dp[j] + 1$（其中$j\in fromList[i]$）。

• 时间复杂度$O(q(n+q))$
• 空间复杂度$O(n+q)$

AC代码

C++

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<int> shortest(n);
        vector<vector<int>> fromList(n);
        for (int i = 1; i < n; i++) {
            fromList[i].push_back(i - 1);
            shortest[i] = i;
        }
        vector<int> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            int from = queries[i][0], to = queries[i][1];
            fromList[to].push_back(from);
            for (int j = to; j < n; j++) {
                for (int from : fromList[j]) {
                    shortest[j] = min(shortest[j], shortest[from] + 1);
                }
            }
            ans[i] = shortest.back();
        }
        return ans;
    }
};

Python

from typing import List

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        shortest = [i for i in range(n)]
        fromList = [[i - 1] for i in range(n)]
        ans = []
        for from_, to in queries:
            fromList[to].append(from_)
            for i in range(to, n):
                shortest[i] = min(shortest[i], min(shortest[j] + 1 for j in fromList[i]))
            ans.append(shortest[-1])
        return ans

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        int[] shortest = new int[n];
        List<Integer>[] fromList = new List[n];
        for (int i = 0; i < n; i++) {
            shortest[i] = i;
            fromList[i] = new ArrayList<Integer>();
            fromList[i].add(i - 1);
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int from = queries[i][0], to = queries[i][1];
            fromList[to].add(from);
            for (int j = to; j < n; j++) {
                for (int from_ : fromList[j]) {
                    shortest[j] = Math.min(shortest[j], shortest[from_] + 1);
                }
            }
            ans[i] = shortest[n - 1];
        }
        return ans;
    }
}

Go

package main

func shortestDistanceAfterQueries(n int, queries [][]int) (ans []int) {
    shortest := make([]int, n)
    fromList := make([][]int, n)
    for i := range shortest {
        shortest[i] = i
        fromList[i] = make([]int, 0)
        fromList[i] = append(fromList[i], i - 1)
    }
    ans = make([]int, len(queries))
    for i, query := range queries {
        fromList[query[1]] = append(fromList[query[1]], query[0])
        for j := query[1]; j < n; j++ {
            for _, from := range fromList[j] {
                shortest[j] = min(shortest[j], shortest[from] + 1)
            }
        }
        ans[i] = shortest[n - 1]
    }
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143897977