[Leetcode] 플로이드와샬 / 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

플로이드와샬

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        
        INF = 1e9
        graph = [[INF] * n for _ in range(n)]
        
        for i in range(n):
            graph[i][i] = 0
        
        #node1, node2, weight
        for [n1,n2,w] in edges:
            graph[n1][n2] = w
            graph[n2][n1] = w
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
        
        
        ret = 0
        retcnt = 101
        
        for a in range(n):
            cnt = 0
            for b in range(n):
                if (a != b and graph[a][b] <= distanceThreshold):
                    cnt += 1
            
            if (retcnt >= cnt):
                ret = a;
                retcnt = cnt
        
        return ret