[백준] 11657번 타임머신

• 알고리즘 : 벨만-포드 알고리즘

• 최단 거리 리스트 구하기
  • 모든 에지를 돌면서
  • (현재 알고 있는 도착지 까지 최단 거리 > 현재 알고 있는 출발지 까지 최단 거리 + 비용) 이면 갱신
  • n-1회 반복

• 음수 사이클 확인하기
  • 다시 한 번 모든 에지를 돌면서
  • (도착지까지 최종 최단 거리 > 출발지까지 최종 최단 거리 + 비용) 인 경우가 한 번이라도 있으면 return True

• 느낀 점
  • 웜홀 문제를 푼 이후라 수월하게 풀 수 있었다

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

• 코드

import sys


def init():
    ipt = sys.stdin.readline
    n, m = map(int, ipt().split())
    edge_list = []
    for _ in range(m):
        a, b, c = map(int, ipt().split())
        edge_list.append((a, b, c))
    return n, edge_list


def bellman_ford():
    dist_list = [float('inf') for _ in range(n+1)]
    dist_list[1] = 0
    for _ in range(n-1):
        for s, e, w in edge_list:
            dist_list[e] = min(dist_list[e], dist_list[s] + w)
    return dist_list


def cycle():
    for s, e, w in edge_list:
        if dist_list[e] > dist_list[s] + w:
            return True
    return False


n, edge_list = init()
dist_list = bellman_ford()
if cycle():
    print(-1)
else:
    for i in range(2, n+1):
        print(dist_list[i] if dist_list[i]!=float('inf') else -1)