Re: [閒聊] 每日leetcode已回收
1334. Find the City With the Smallest Number of Neighbors at a Threshold
Distance
## 思路
對每個city做Dijkstra
## Complexity
Time: O(N^3 log N) # 單獨Dijkstra是 O(E log V) = O(N^2 logN)
Space: O(N^2) # Graph
## Code
```python
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold:
int) -> int:
graph = defaultdict(list)
for a, b, weight in edges:
graph[a].append((b, weight))
graph[b].append((a, weight))
res_city, res_count = -1, float('inf')
for i in range(n-1, -1, -1):
heap = [(0, i)]
seen = {i: 0}
while heap:
dist, city = heapq.heappop(heap)
for neighbor, weight in graph[city]:
if dist + weight > distanceThreshold:
continue
if neighbor not in seen or seen[neighbor] > dist + weight:
seen[neighbor] = dist + weight
heapq.heappush(heap, (dist + weight, neighbor))
count = len(seen) - 1
if count < res_count:
res_city, res_count = i, count
return res_city
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721968916.A.608.html
→
07/26 12:42,
1年前
, 1F
07/26 12:42, 1F
改了一下code, heap 寫成 queue
我好廢
※ 編輯: dont (185.213.82.36 臺灣), 07/26/2024 14:45:35
討論串 (同標題文章)
完整討論串 (本文為第 567 之 1554 篇)：