1. 문제 설명

타임머신

2. 문제 분석

벨만-포드 알고리즘은 특정 노드로부터의 다른 모든 노드에 대한 최단 거리를 구하는 방법이다. 다익스트라 알고리즘보다 시간 복잡도는 좋지 않지만 음수 가중치를 구할 수 있으므로 범용성이 있다. 음수 사이클이 존재할 때 문제를 풀 수 없기 때문에 정점 개수만큼의 반복 시 갱신이 되는지 확인한다.

3. 나의 풀이

import sys

INF = sys.maxsize
n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c])

def B_F(start):
    # 벨만-포드 알고리즘
    distances = [INF for _ in range(n+1)]
    distances[start] = 0
    # 시작 노드 자기 자신에 대한 거리는 0으로 초기화

    for i in range(n):
        # 정점 개수만큼 반복
        for cur_node in range(1, n+1):
            for next_node, next_cost in nodes[cur_node]:
                if distances[next_node] > distances[cur_node] + next_cost and distances[cur_node] != INF:
                    # 업데이트 가능
                    if i == n-1: return -1
                    # 업데이트 가능하지만 n번째 반복 시 업데이트는 곧 음수 사이클이 존재함을 의미
                    distances[next_node] = distances[cur_node] + next_cost
    return distances
flag = B_F(1)
if flag == -1: print(-1)
else:
    distances = flag
    for i in range(2, n+1):
        if distances[i] == INF:
            print(-1)
            # 거리 무한은 곧 해당 노드에 대한 경로가 존재하지 않음을 의미
        else: print(distances[i])