Re: [閒聊] 每日leetcode

[dont (dont)]

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
→ JIWP: 別卷了
改了一下code, heap 寫成 queue
我好廢
※ 編輯: dont (185.213.82.36 臺灣), 07/26/2024 14:45:35