[백준] 11657번 타임머신

💡문제접근

• 가중치 C가 양수가 아닌 경우도 존재하므로 벨만-포드 알고리즘을 이용해서 최단 경로를 구할 수 있다.

💡코드(메모리 : 32276KB, 시간 : 744ms)

import sys
input = sys.stdin.readline
INF = int(1e9)

def bf(start):
    dist[start] = 0
    for i in range(N):
        for j in range(M):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                dist[next_node] = dist[cur] + cost
                if i == N-1:
                    return True
    return False

N, M = map(int, input().strip().split())
dist = [INF] * (N+1)
edges = []

for _ in range(M):
    A, B, C = map(int, input().strip().split())
    edges.append([A, B, C])

negative_cycle = bf(1)

# 1번 도시에서 출발해 어떤 도시로 가는 과정에서 무한히 오래 전으로 되돌릴 수 있다면?
if negative_cycle:
    print(-1)
else:
    for i in range(2, N+1):
        # 해당 도시로 가는 경우가 존재하지 않는다면?
        if dist[i] == INF:
            print(-1)
        else:
            print(dist[i])

💡소요시간 : 24m