👉문제 링크

느낀점

• 어렵다ㅋㅋㅋ
• 벨만포드 문제를 풀어보았다.
• 나중에 다시 보는 걸로..
• 참고한 곳: https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

정답 코드 및 해설

N, M = map(int, input().split())

possible = True
nodes = [float('inf') for _ in range(N)]
nodes[0] = 0
edges = []

for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, c])

for _ in range(M-1):
    for i in range(M):
        a, b, c = edges[i]
        if nodes[a] != float('inf'):
            temp = nodes[a] + c
            if temp < nodes[b]:
                nodes[b] = temp

for i in range(M):
    a, b, c = edges[i]
    if nodes[a] != float('inf'):
        temp = nodes[a] + c
        if temp < nodes[b]:
            possible = False

if possible:
    for node in nodes[1:]:
        if node != float('inf'):
            print(node)
        else:
            print(-1)
else:
    print(-1)