백준 11657 - 합이 0인 네 정수 (Python)

깃허브:

https://github.com/MSIQOC/BOJ/blob/master/b11657_%ED%83%80%EC%9E%84%EB%A8%B8%EC%8B%A0.py

GitHub - MSIQOC/BOJ: 백준 문제들에 대한 저의 풀이가 포함돼있습니다.

 

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

11657번: 타임머신

https://msiqoc.tistory.com/34

벨만포드 알고리즘

벨만포드 알고리즘을 써서 풀면 되는 문제이다.

키워드: x도시에서 y도시로 가는 가장 빠른 시간, [음수]인 시간 존재.

 

---

Python

#
# Created by MinSeo on 2022/02/09.
# Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
#
 
inf = float('inf')
n, m = map(int, input().split())
 
edge = []
dist = [inf] * (n+1)
for i in range(m):
    a, b, c = map(int, input().split())
    edge.append((a, b, c))
 
 
def bellman(start):
    dist[start] = 0
    for v in range(n):
        for i in range(m):
            s = edge[i][0]
            c = edge[i][2]
            e = edge[i][1]
            if dist[s] != inf and dist[e] > c + dist[s]:
                dist[e] = c + dist[s]
                if v == n-1:
                    return True
    return False
 
 
if bellman(1):
    print(-1)
else:
    for i in range(2, len(dist)):
        print(dist[i]) if dist[i] != inf else print(-1)