一、问题描述
给你一个整数 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。
from typing import Listq = [[2, 4], [0, 2], [0, 4]]class Solution:def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:links = [[i + 1] for i in range(n)] # links[i]表示城市i连接的其他城市j, 初始每个城市i连接其下一个城市i+1dp = [i for i in range(n)] # dp[i]表示0的到i的最短路径长度, 初始每个城市i到0的最短路径长度为ianswer = [] # answer[i]表示第i个查询的答案for u, v in queries: # 得到一条连接u->vif u < v - 1: # u < v-1，这样保证不走回头路dp[v] = min(dp[v], dp[u] + 1) # 首先0到v多了一条新的路径：0->u->v，更新路径长度for j in range(v, n - 1): # 由于v被改变了，那么和[v, n-2]城市的相连的城市路径都应该更新for k in links[j]:dp[k] = min(dp[k], dp[j] + 1) # 更新城市j->它直接连接的城市k的最小距离links[u].append(v) # 更新城市u连接的城市answer.append(dp[n - 1]) # 更新后的dp[n-1]就是答案return answerS= Solution()
print(S.shortestDistanceAfterQueries(5,q))二、结果展示
[3, 2, 1]
