import sys
input = sys.stdin.readline
INF = int(1e9)
v, e = map(int, input().split())
g = [[INF] * v for _ in range(v)]
for _ in range(e):
a, b, c = map(int, input().split())
g[a-1][b-1] = c
for k in range(v):
for i in range(v):
for j in range(v):
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = INF
for i in range(v):
ans = min(ans, g[i][i])
if ans == INF:
print(-1)
else:
print(ans)
처음 짠 코드(통과) : 처음에 자기자신에게 가는 경로를 없다고 가정하고 0으로 초기화하지 않고 무한대로 두고 플로이드 와샬함
import sys
input = sys.stdin.readline
INF = int(1e9)
v, e = map(int, input().split())
g = [[INF] * v for _ in range(v)]
for _ in range(e):
a, b, c = map(int, input().split())
g[a-1][b-1] = c
for i in range(v):
g[i][i] = 0
for k in range(v):
for i in range(v):
for j in range(v):
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
ans = INF
for i in range(v):
for j in range(v):
ans = min(ans, g[j][i] + g[i][j])
if ans == INF:
print(-1)
else:
print(ans)
아예 자기 자신으로 가는 경로를 무한대로 두고 플로이드 와샬하고 나중에 자기 자신 -> 임의의 노드 -> 자기 자신으로 가는 경로 (사이클) 중 최단거리 찾음
=> 왜 안됨??for i in range(v): for j in range(v): if i != j: ans = min(ans, g[j][i] + g[i][j])
이렇게 자기 자신으로 가는 경로 빼주니까 된다. 자기 자신은 위에서 0이라고 하고 ... 카운트 함...