[백준] 1956번-(Python 파이썬) - Floyd-Warshall

문제링크 : https://www.acmicpc.net/problem/1956

이번 문제도 플로이드 와샬 알고리즘으로 쉽게 풀 수 있다.
마지막에 시작점과 도착점이 자기자신인 값 중 가장 작은 값만 구해주면 된다.

import sys

input = sys.stdin.readline
inf = sys.maxsize

v, e = map(int, input().split())
dist = [[inf] * v for _ in range(v)]

for _ in range(e):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c

for k in range(v):
    for i in range(v):
        for j in range(v):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

ans = inf
for i in range(v):
    ans = min(ans, dist[i][i])

print(ans if ans != inf else -1)