Question

Code

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        adj = defaultdict(list)

        for a, b, weight in edges:
            adj[a].append((weight, b))
            adj[b].append((weight, a))

        shortest_path = {}

        def dijkstra(src):

            que = [(0, src)]
            visited = set()

            while que:
                cur_weight, cur_node = heapq.heappop(que)

                if cur_node in visited:
                    continue

                visited.add(cur_node)
                shortest_path[(src, cur_node)] = cur_weight

                for nei_weight, nei_node in adj[cur_node]:
                    if nei_node in visited:
                        continue
                    heapq.heappush(que, (nei_weight + cur_weight, nei_node))

        for i in range(n):
            dijkstra(i)

        neighbors = [0] * n 

        for i in range(n):
            for j in range(n):
                if i != j and (i, j) in shortest_path and shortest_path[(i, j)] <= distanceThreshold:
                    neighbors[i] += 1

        elem = min(neighbors)

        for i in range(n - 1, -1, -1):
            if neighbors[i] == elem:
                return i