Re: [閒聊] 每日leetcode
3243. Shortest Distance After Road Addition Queries I
## 思路
先建初始Graph (i -> i+1)
並記錄0到每個點的距離dist
每個Query加一個邊(src, dst)到Graph
檢查dist[dst], 有縮短就跑BFS更新後面的dist
## Code
```python
class Solution:
def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]])
-> List[int]:
graph = defaultdict(list)
for i in range(n-1):
graph[i].append(i+1)
dist = [i for i in range(n)]
def add_road(src, dst):
graph[src].append(dst)
if dist[dst] <= dist[src] + 1:
return dist[-1]
dist[dst] = dist[src] + 1
queue = deque([dst])
while queue:
city = queue.popleft()
for next_city in graph[city]:
if dist[next_city] <= dist[city] + 1:
continue
dist[next_city] = dist[city] + 1
queue.append(next_city)
return dist[-1]
return [add_road(src, dst) for src, dst in queries]
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.184 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732713491.A.838.html
討論串 (同標題文章)
完整討論串 (本文為第 1160 之 1548 篇)：