3243. Shortest Distance After Road Addition Queries I
現學現賣BFS
queue 記錄 (點, 搜到時的路徑長)
neighbor 找到最後一點時就直接返回
class Solution:
def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -
> List[int]:
def bfs(graph: dict, start, target):
road = 0
queue = deque([(start, road)])
result = []
visited = set()
visited.add(start)
while queue:
current, road = queue.popleft()
result.append(current)
road += 1
for neighbor in graph.get(current, []):
if neighbor == target:
return road
if neighbor not in visited:
queue.append((neighbor, road))
visited.add(neighbor)
return road
graph = {i: [i+1] for i in range(n-1)}
answer = []
for a, b in queries:
graph[a].append(b)
answer.append(bfs(graph, 0, n-1))
return answer