[백준 1956] 운동 - Python(파이썬)

 

from heapq import heappush, heappop
import sys


# 다익스트라 구현
def solution(x):
    check = [inf] * (V + 1)
    temp = [(0, x)]

    while temp:
    	# w: 거리, idx: 해당 인덱스
        w, idx = heappop(temp)
        # 인덱스가 x라는 것은 가장 짧게 한 사이클을 돌았다는 것을 의미
        if x == idx and w != 0:
            break
        if check[idx] >= w:
            for i, d in dist[idx]:
                d += w
                if check[i] > d:
                    check[i] = d
                    heappush(temp, (d, i))

    return check[x]


V, E = map(int, sys.stdin.readline().split())
inf = float('inf')
dist = {i: [] for i in range(1, V + 1)}

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    dist[a].append((b, c))

answer = inf

for x in dist.keys():
    if len(dist[x]):
        answer = min(answer, solution(x))

print(answer if answer != inf else -1)