[백준] 11657번 - 타임머신 (파이썬)

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

# 타임머신
import sys
input = sys.stdin.readline
MAX = sys.maxsize
N, M = map(int, input().split())
bus = []
for _ in range(M):
    a, b, time = map(int, input().split())
    bus.append((a, b, time))
dist = [MAX] * (N+1)


def bf(start):
    dist[start] = 0
    for k in range(N):
        for i in range(M):
            city, ncity, time = bus[i]
            if dist[city] != MAX and dist[ncity] > dist[city] + time:
                dist[ncity] = dist[city] + time
                if k == N-1:
                    return True
    return False

if bf(1):
  print('-1')
else:
  for i in range(2, N+1):
    if dist[i] == MAX:
      print('-1')
    else:
      print(dist[i])

 

최단거리, 벨만포드

1. 총 노드의 수 만큼 모든 버스 노선을 확인한다

    - dist가 더 작은 값으로 업데이트를 해준다

    - 만약 마지막 반복에서도 dist의 값이 업데이트가 된다면 (음수의 순환 발생) retrun true

2. 음수의 순환이 발생하면 print(-1) 아니면 다른 노드들 까지의 최단 거리 출력

 

방향성이 있는 그래프 + 간선이 양수 = 다익스트라

방향성이 있는 그래프 + 간선에 음수 포함 = 벨만포드