[파이썬] 백준 11657 : 타임머신 (골드4)

[파이썬] 백준 11657 : 타임머신 (골드4)

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

---

풀이

방향성 생각

• 음수간선이 포함된 벨만 포드문제
• V-1번의 안정화 과정, 1번의 음수 사이클 탐지를 확인한다.

 

---

파이썬

import sys

input = lambda : sys.stdin.readline().strip()
INF = float('inf')

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

G = [tuple(map(int,input().split())) for _ in range(M)]

def bf(sx):

    V = [INF]*(N+1)
    V[sx] = 0

    for n in range(N):
        for a,b,cost in G:
            if V[a] + cost < V[b]:
                V[b] = V[a] + cost
                if N-1 == n:
                    return -1
    return V

answer = bf(1)
if type(answer) == list:
    for i in range(2,N+1):
        print(answer[i] if answer[i] != INF else -1)
else:
    print(answer)

---

코멘트

• N-1번의 안정화 과정이 끝난 후, visit 배열이 업데이트 되는지 확인한다.