[Python] 백준 알고리즘 #1956 운동 (플로이드 와샬 알고리즘)

문제

1956번: 운동

풀이

플로이드 와샬 알고리즘을 통해서 풀면 된다. 

먼저 가로세로 마을 갯수만큼의 2차원 배열을 만든 후, i부터 j까지의 거리값을 arr[i][j] 에 넣어줬다.

그 후, 거쳐가는애를 하나 정하고(k) i에서 j까지 갈때 바로가는게 빠른지, k를 거쳐가는게 빠른지 판단한 후 더 빠른 값으로 arr[i][j]를 갱신해주면 된다.

그렇게 계속 돌리면 나중에는 결국 arr[i][i]에 있는 값이 i에서 다시 i로 돌아오는 가장 빠른 사이클의 값이 된다. 

import sys

# V: 마을 갯수, E: 도로 갯수
V, E = map(int, sys.stdin.readline().split())

INF = sys.maxsize
arr = [[INF for _ in range(V)] for _ in range(V)]

for _ in range(E):
    i, j, c = map(int, sys.stdin.readline().split())
    arr[i-1][j-1] = c

for k in range(V):  # 거쳐가는애
    for i in range(V):  # from
        for j in range(V):  # to
            arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])

result = INF
#  계속 갱신한 뒤 사이클은 본인부터 본인까지에 저장됨
for i in range(V):
    result = min(result, arr[i][i])

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

 

 

(아무래도 시간이 오래걸릴듯해서 pypy로 제출)