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 neighbor not in seen or seen[neighbor] > dist + weight:
seen[neighbor] = dist + weight
heapq.heappush(heap, (dist + weight, neighbor))
count = sum(dist <= distanceThreshold for dist in seen.values())
if count < res_count:
res_city, res_count = i, count
return res_city
```