Re: [閒聊] 每日leetcode
看板Marginalman作者JerryChungYC (JerryChung)時間1年前 (2024/11/28 05:18)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1163/1548 (看更多)
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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.45.12.183 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732742280.A.97D.html
討論串 (同標題文章)
完整討論串 (本文為第 1163 之 1548 篇)：