플로이드와샬
-
[Leetcode] 플로이드와샬 / 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance알고리즘 2022. 6. 11. 21:32
플로이드와샬 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 r..