Floyd-Warshall Algorithm플로이드-워셜

dp[i][j][k] = 정점 0~k를 거쳐서 i→j까지의 최단 거리

점화식:
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

INF = float('inf')

def floyd_warshall(n, edges):
    dist = [[INF]*n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 음수 사이클 탐지: dist[i][i] < 0이면 존재