[백준] 1956번 운동

💡문제접근

• 플로이드-워셜 알고리즘의 시간복잡도는 O(N^3)
• Python3로는 시간초과, PyPy3로는 AC
• 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다. → 자기 자신에서 자기 자신으로 이동하는 경우를 0으로 계산하지 않는다.

💡코드(메모리 : 116528KB, 시간 : 1020ms, PyPy3로 제출)

import sys
input = sys.stdin.readline
INF = int(1e9)

V, E = map(int, input().strip().split())
graph = [[INF] * (V+1) for _ in range(V+1)]

for _ in range(E):
    a, b, c = map(int, input().strip().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(-1)
else:
    print(answer)

💡소요시간 : 27m