1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        graph = {i: [] for i in range(n)}
        for f, t, weight in edges:
            graph[f].append((weight, t))
            graph[t].append((weight, f))
        
        def findNeighbors(x):            
            weights = [float("inf")] * n
            weights[x] = 0
            min_heap = [(0, x)]
            
            while min_heap:
                weight, node = heapq.heappop(min_heap)
                if weight > distanceThreshold:
                    break
                for w, neighbor in graph[node]:
                    if weights[neighbor] > weight + w:
                        weights[neighbor] = weight + w
                        heapq.heappush(min_heap, (weights[neighbor], neighbor))
            count = 0
            for w in weights:
                if w <= distanceThreshold:
                    count += 1
            return count
        
        city = -1
        neighbors = n
        for i in range(n):
            num_neighbors = findNeighbors(i)
            if num_neighbors <= neighbors:
                neighbors = num_neighbors
                city = i
        return city

Time complexity is O(V * ElgE)