[Algorithm][벨만포드] 백준 11657 : 타임머신

"""
BOJ 타임머신 문제 (https://www.acmicpc.net/problem/11657)
1<=N<=500
1<=M<=6000

1. 아이디어
- 모든 간선 확인
- 음의 간선 존재 => 벨만포드 알고리즘

2. 시간복잡도
- O(VE)

3. 자료구조

"""
import sys
input = sys.stdin.readline

N,M = map(int, input().split())
edges = [] #간선 테이블
INF = int(1e9)
distance = [INF]*(N+1) #최단 거리 테이블

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

def bellmanford(start):
    distance[start]=0
    for i in range(N):
        for j in range(M): #매 반복마다 모든 간선 확인
            cur = edges[j][0]
            next = edges[j][1]
            cost = edges[j][2]
            
            if distance[cur] != INF and distance[next] > distance[cur] + cost: ### 
                distance[next] = distance[cur] + cost
                if i==N-1:
                    return True
    return False


negative_cycle = bellmanford(1)

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

 

참고 - 이코테 파이썬