[백준/파이썬] 11657번

📍백준 11657 문제

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

코드

import sys
input = sys.stdin.readline

m, n = map(int, input().split())
edge = []
dist = [sys.maxsize] * (m+1)

dist[1] = 0
for _ in range(n):
    a, b, c = map(int, input().split())
    edge.append((a, b, c))

isCycle = False
for i in range(m):
    for start, end, c in edge:
        if dist[start] != sys.maxsize:
            distance = dist[start] + c
            if distance < dist[end]:
                if i == m-1:
                    isCycle = True
                dist[end] = distance
if isCycle:
    print(-1)
else:
    for i in dist[2:]:
        if i == sys.maxsize:
            print(-1)
        else:
            print(i)

풀이

벨만-포드 알고리즘을 이용해 문제를 푼다.
dist[2:]인 이유는 0번엔 값이 없고 1번은 출발했기 때문에 그렇다..!