[BOJ] Python 백준 타임머신(11657)

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

 

전형적인 음수 간선 판단 문제이다.

벨만포드를 이용하여 내부에서 음수 간선으로 인해 비용 감소가 계속 발생할 경우 -1을 출력하면 된다.

import sys
input = sys.stdin.readline

N,M = map(int,input().split())

edges = []
distance = [float('inf')] * (N+1)

def bf(start):
    distance[start] = 0

    for i in range(N):
        for j in range(M):
            s,e,cost = edges[j]
            if distance[e] > distance[s] + cost:
                distance[e] = distance[s] + cost
                if i == N-1:
                    return True
    return False

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


chk = bf(1)

if chk:
    print(-1)

else:
    for i in range(2,N+1):
        if distance[i] != float('inf'):
            print(distance[i])
        else:
            print(-1)

 

회고.

오랜만에 푸니까 벨만포드 알고리즘을 기억하는데 시간이 좀 걸렸다. 원활하게 바로 구현할 수 있도록 항상 염두해두고 있어야 겠다.