BOJ 1956번: 운동

https://www.acmicpc.net/problem/1956

1956번: 운동

문제풀이:

플로이드 와샬 알고리즘을 사용하여 문제를 풀었고, pypy로 통과했다.

플로이드 와샬 알고리즘을 사용해야겠다고 생각하는 게 어려운 것 같다.

 

import sys

V, E = map(int, sys.stdin.readline().split())
INF = 10**10
graph = [[INF]*(V+1) for _ in range(V+1)]
for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = c

for k in range(1,V+1):
    for i in range(1,V+1):
        for j in range(1,V+1):
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

ans = INF
for i in range(1,V+1):
    ans = min(ans, graph[i][i])

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