[백준/파이썬] #11657

음수 간선이 존재한다는 걸 알자 벨만 포드 알고리즘을 써야겠다고는 생각했다. 그런데 정확히 해당 알고리즘이 어떻게 되어있는지는 기억이 잘 안 나서, 풀이는 아니지만 다른 블로그 글을 참고했다. 

 

알고보니 설명하는 로직을 그대로 문제에 적용하면 답이 풀리더라... 뭔가 답지를 본 느낌이 들었지만 일단 내가 쓴 풀이를 가져와봤다. 

import sys

input = sys.stdin.readline
INF = 1e9

N, M = map(int, input().split())
dist = [INF] * (N+1)
edges = []
start = 1
for _ in range(M):
    A, B, C = map(int, input().split())
    edges.append((A, B, C))

dist[start] = 0
negative_cycle = False
for i in range(N):
    for j in range(M):
        curNode, nextNode, edgeCost = edges[j]
        if dist[curNode] != INF and dist[curNode] + edgeCost < dist[nextNode]:
            dist[nextNode] = dist[curNode] + edgeCost
            if i == N-1:
                negative_cycle = True
                break

if negative_cycle:
    print(-1)
else:
    for i in range(2, N+1):
        if dist[i] == INF:
            print(-1)
        else:
            print(dist[i])