[백준]1956 운동 #플로이드와샬#사이클

1. 풀이

플로이드와샬을 이용해서 사이클을 구한다.

처음에 i->i로 가는 가중치를 INF로 주고, 플로이드와샬을 한번 수행한 뒤, i->i 값이 변해있으면 i->i로 가는 사이클이 존재한다는 뜻.

이때 가중치가 사이클 도로의 합이므로 그중 최소를 찾는것이 정답이 된다.

​

2. 소스코드

import sys

INF = 9876543210
V, E = map(int, input().split())
L=[[0 for j in range(V)] for i in range(V)]

for i in range(V):
    for j in range(V):
        L[i][j]=INF

for i in range(E):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    L[a-1][b-1]=c

for k in range(V):
    for i in range(V):
        for j in range(V):
            if L[i][j]>L[i][k]+L[k][j]:
                L[i][j]=L[i][k]+L[k][j]

ans=INF
for i in range(V):
    if L[i][i]<ans:
        ans=L[i][i]

if ans==INF:
    print(-1)
else:
    print(ans)