[백준/Python] 11657번 타임머신 - (벨만 포드)

문제

https://www.acmicpc.net/problem/11657

소스코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

grape = {}
for i in range(m):
    a, b, c = map(int, input().split())
    if a not in grape:
        grape[a] = []
    grape[a].append((b, c))

def bellman_ford(start):
    distance_list = [1e9] * (n + 1)
    distance_list[start] = 0
    
    for i in range(n - 1):
        for u in grape:
            for v, w in grape[u]:
                if distance_list[u] != 1e9 and distance_list[u] + w < distance_list[v]:
                    distance_list[v] = distance_list[u] + w
    for u in grape:
        for v, w in grape[u]:
            if distance_list[u] != 1e9 and distance_list[u] + w < distance_list[v]:
                return None
    return distance_list
data = bellman_ford(1)
if data == None:
    print(-1)
else:
    for i in range(n-1):
        if data[i + 2] >= 1e9:
            print(-1)
        else:
            print(data[i + 2])

 

벨만포드 알고리즘 문제입니다.

벨만포드 알고리즘은 간선의 가중치가 음수일때도 성립이 되고, 음수 사이클을 찾을 수 있습니다. 

벨만포드 알고리즘의 시간 복잡도는 O(VE)입니다.