BOJ - 1956

백준 문제 링크
운동

❓접근법

1. 플로이드 워셜 알고리즘을 사용했다.
2. 기존 플로이드 워셜 알고리즘에서는 자기 자신에게 가는 비용이 0 인데,
   여기서는 사이클을 구해야 하므로 0 처리를 하지 않았다.
3. 플로이드 워셜 소스코드를 전개하고,
   answer = INF로 지정한다.

• graph에서 행과 열이 같을 때,
  answer = min( answer, graph[i][i] )로 변환해준다.

4. answer == INF이면 -1, 아니면 answer를 출력한다. 끝!

👌🏻코드

v, e = map(int, input().split())

INF = int(1e9)

graph = [[INF] * (v + 1) for _ in range(v + 1)]
            
for _ in range(e):
    a, b, c = map(int, input().split())
    
    graph[a][b] = c
    
for k in range(1, v + 1):
    for a in range(1, v + 1):
        for b in range(1, v + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            
answer = INF

for i in range(1, v + 1):
    answer = min(answer, graph[i][i])

if answer != INF:
    print(answer)
else:
    print(-1)