059 타임머신

첫번째 코드

 

벨만-포드는 음수가 가능하고

사이클이 있는 경우 확인이 가능하다.

 

뭔가 다익스트라와 비슷한 유형의 문제라고 느꼈는데

위의 경우를 제외하고 언제 사용하는게 더 효율적인지는 잘 모르겠다!

 

코드는 책을 참고했는데

여전히 어렵고 다음에 꼭 다시 풀어야겠다...

문제가 어려워서 그런가 점점 그냥 따라쓰는 기분...

 

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
A = []
distance = [sys.maxsize] * (n+1)

for i in range(m):
    s, e, t = map(int, input().split())
    A.append((s, e, t))

distance[1] = 0

for _ in range(n-1):
    for s, e, t in A:
        if distance[s] != sys.maxsize and distance[e] > distance[s] + t:
            distance[e] = distance[s] + t

cycle = False

for s, e, t in A:
    if distance[s] != sys.maxsize and distance[e] > distance[s] + t:
           cycle = True

if not cycle:
     for i in range(2, n+1):
        if distance[i] != sys.maxsize:
            print(distance[i])
        else:
            print(-1)
else:
    print(-1)

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/11657.%E2%80%85%ED%83%80%EC%9E%84%EB%A8%B8%EC%8B%A0

programmers/백준/Gold/11657. 타임머신 at main · ornni/programmers