[백준] 11657번-(Python 파이썬) - Bellman-Ford

문제링크 : https://www.acmicpc.net/problem/11657

이번 문제는 가중치가 음수인 경우가 있어 다익스트라가 아니라 벨만포드 알고리즘으로 풀어야한다.
벨만포드 알고리즘은 다익스트라에 비해 느리므로 가중치가 음수인경우에만 사용하는게 좋다.

기본적인 다익스트라로 풀 수 없는 이유는 음수 간선이 존재할 때 사이클을 순환할수록 가중치가 감소하는 경우가 생겨서 이 경우에 순환하고 도착점에 도달하더라도 실질적인 최단경로라고 볼 수는 없기 때문에 벨만포드 알고리즘으로 풀어주어야한다.

import sys
input = sys.stdin.readline
inf = sys.maxsize

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
dp = [inf] * (n + 1)
dp[1] = 0
isPossible = True

def bellmanFord():
    global isPossible
    
    for repeat in range(n):
        for i in range(1, n + 1):
            for n_n, wei in graph[i]:
                if dp[i] != inf and dp[n_n] > dp[i] + wei:
                    dp[n_n] = dp[i] + wei
                    if repeat == n - 1:
                        isPossible = False

for _ in range(m):
    a, b, c = map(int ,input().split())
    graph[a].append([b, c])


bellmanFord()

if not isPossible:
    print(-1)
else:
    for i in dp[2:]:
        print(i if i != inf else -1)