给你一个整数 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。
代码：
class Solution:
def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
g = [[i+1] for i in range(n-1)]
vis =[-1]*(n-1)
def bfs(i:int)->int: #广度优先搜索
q = deque([0])
for step in count(1):
tmp = q
q = []
for x in tmp:
for y in g[x]:
if y==n-1:
return step
if vis[y] !=i:
vis[y] = i
q.append(y)
return -1
ans = [0]*len(queries)
for i,(l,r) in enumerate(queries):
g[l].append(r)
ans[i] = bfs(i)
return ans
对于广度优先搜索代码每一运行的说明
通过一个具体的例子来演示bfs函数的运行过程。假设我们有以下简化的数据和查询：
- 数组长度
n = 5，所以数组索引从0到4。 - 图
g初始化为：[[1], [2], [3], [4]]，表示每个索引指向下一个索引。 - 查询
queries = [[1, 3]]，表示在索引1和3之间增加一个连接。 vis初始化为[-1, -1, -1, -1]。
现在，我们执行查询 [1, 3] 后，更新图 g 为：[[1], [2, 3], [3], [4]]。
接下来，我们调用 bfs(0) 来找到从索引0到索引4的最短路径长度。
初始化
q = deque([0])：队列初始化，包含起始节点0。vis = [-1, -1, -1, -1]：访问数组初始化，表示所有节点都未被访问过。
第一步（step = 1）
- 从队列中取出节点0，访问其邻居
[1]。 - 将节点1加入队列，
q = deque([1])。 - 标记节点1为已访问，
vis = [-1, 0, -1, -1]。
第二步（step = 2）
- 从队列中取出节点1，访问其邻居
[2, 3]。 - 将节点2和3加入队列，
q = deque([2, 3])。 - 标记节点2和3为已访问，
vis = [-1, 0, 0, 0]。
第三步（step = 3）
- 从队列中取出节点2，访问其邻居
[3]。由于节点3已在队列中，我们不再重复添加。 - 节点3已经在队列中，我们不需要再次处理。
- 从队列中取出节点3，访问其邻居
[4]。 - 将节点4加入队列，
q = deque([4])。 - 标记节点4为已访问，
vis = [-1, 0, 0, 0, 0]。
第四步（step = 4）
- 从队列中取出节点4，没有未访问的邻居。
在这一步，我们发现无法从节点4继续前进，因为所有节点都已访问过。但是，我们的目标是找到从节点0到节点4的最短路径。在第三步中，我们已经找到了这条路径：0 -> 1 -> 2 -> 3 -> 4。
因此，bfs函数返回的步数是3，表示从节点0到节点4的最短路径需要3步。
请注意，这个例子是为了演示bfs函数的运行过程而简化的。在实际的shortestDistanceAfterQueries问题中，图的更新和BFS的执行会更加复杂，因为每次查询都可能影响图的结构。
这里，节点 1 现在有两个邻居：节点 2 和节点 3。这种更新模拟了查询操作，即在位置 1 和位置 3 之间的元素距离减少，因为现在存在一条直接的连接。而且通常这使用于无向图。
一些细节
-
for y in g[x]:：这行代码遍历当前节点x的所有邻居节点y。g[x]是一个列表，包含了节点x直接连接的所有节点。 -
if y==n-1: return step：这行代码检查当前节点y是否是数组的结束位置（索引n-1）。如果是，这意味着我们找到了从起始位置到结束位置的一条路径，并且step变量记录了这条路径的长度（步数）。一旦找到路径，函数就返回当前的步数。 -
if vis[y] != i:：这行代码检查节点y是否已经被当前的查询i访问过。vis数组用于跟踪每个节点在当前查询中是否被访问过，以避免重复访问和无限循环。 -
vis[y] = i：如果节点y没有被当前查询访问过，这行代码将vis[y]设置为当前查询的索引i，标记节点y为已访问。 -
q.append(y)：将未访问的邻居节点y添加到队列q的末尾。在下一次迭代中，这些节点将被处理，它们的邻居也将被检查。
思路2：动态规划
class Solution:
def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
frm = [[] for _ in range(n)]
f = list(range(n))
ans = []
for l, r in queries:
frm[r].append(l)
if f[l] + 1 < f[r]:
f[r] = f[l] + 1
for i in range(r + 1, n):
f[i] = min(f[i], f[i - 1] + 1, min((f[j] for j in frm[i]), default=inf) + 1)
ans.append(f[-1])
return ans