LeetCode 题解工作台
新增道路查询后的最短距离 I
给你一个整数 n 和一个二维整数数组 queries 。 有 n 个城市，编号从 0 到 n - 1 。初始时，每个城市 i 都有一条 单向 道路通往城市 i + 1 （ 0 ）。 queries[i] = [u i , v i ] 表示新建一条从城市 u i 到城市 v i 的 单向 道路。每次查…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们先建立一个有向图 ，其中 表示从城市 出发可以到达的城市列表，初始时，每个城市 都有一条单向道路通往城市 $i + 1$。 然后，我们对每个查询 $[u, v]$，将 添加到 的可达城市列表中，然后使用 BFS 求出从城市 到城市 $n - 1$ 的最短路径长度，将结果添加到答案数组中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个整数 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 <= 5001 <= queries.length <= 500queries[i].length == 20 <= queries[i][0] < queries[i][1] < n1 < queries[i][1] - queries[i][0]- 查询中没有重复的道路。
解题思路
方法一：BFS
我们先建立一个有向图 ，其中 表示从城市 出发可以到达的城市列表，初始时，每个城市 都有一条单向道路通往城市 。
然后，我们对每个查询 ，将 添加到 的可达城市列表中，然后使用 BFS 求出从城市 到城市 的最短路径长度，将结果添加到答案数组中。
最后返回答案数组即可。
时间复杂度 ，空间复杂度 。其中 和 分别为城市数量和查询数量。
class Solution:
def shortestDistanceAfterQueries(
self, n: int, queries: List[List[int]]
) -> List[int]:
def bfs(i: int) -> int:
q = deque([i])
vis = [False] * n
vis[i] = True
d = 0
while 1:
for _ in range(len(q)):
u = q.popleft()
if u == n - 1:
return d
for v in g[u]:
if not vis[v]:
vis[v] = True
q.append(v)
d += 1
g = [[i + 1] for i in range(n - 1)]
ans = []
for u, v in queries:
g[u].append(v)
ans.append(bfs(0))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(q * (n + q)) because each of the q queries may trigger a BFS exploring up to n nodes plus previously added q roads. Space complexity is O(n + q) to store the adjacency list for n nodes and all added roads. |
| 空间 | O(n+q) |
面试官常问的追问
外企场景- question_mark
Check if the candidate efficiently updates the graph structure after each query.
- question_mark
Watch for early BFS termination when city n - 1 is found to optimize performance.
- question_mark
Listen for reasoning about incremental shortest path updates versus full recomputation.
常见陷阱
外企场景- error
Recomputing the entire shortest path from scratch for every query without incremental tracking.
- error
Ignoring early stopping in BFS and exploring unnecessary nodes.
- error
Failing to handle cases where no path exists after a road addition.
进阶变体
外企场景- arrow_right_alt
Allow bidirectional road additions instead of unidirectional, requiring modified BFS.
- arrow_right_alt
Return the full shortest path sequence from 0 to n - 1 after each query instead of just the length.
- arrow_right_alt
Process a larger graph with sparse updates using a priority queue to improve BFS efficiency.