알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 59. 타임머신으로 빨리 가기

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

문제

N개의 도시와 한 도시에서 출발해 도착하는 버스가 M개 있다. A는 시작 도시, B는 도착 도시, C는 버스를 타고 이동하는 데 걸리는 시간

C가 양수가 아닐 때도 있음. 1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간을 구하기

 

최단거리

1. 다익스트라

2. 벨만 포드 -> 음수 간선이 있음

3. 플로이드 워셜

 

코드

import sys

input = sys.stdin.readline

n, e = map(int, input().split())

# 에지 리스트로 그래프 구현
graph = []
for i in range(e):
    u, v, w = map(int, input().split())
    graph.append((u,v,w))
    
# 벨만 포드 알고리즘
dist = [float('inf')] * (n+1)
dist[1] = 0

for _ in range(n-1):
    for s, e, w in graph:
        if dist[s] != float('inf') and dist[e] > dist[s] + w:
            dist[e] = dist[s] + w
        
for s, e, w in graph:
    if dist[s] != float('inf') and dist[e] > dist[s] + w:
        print(-1)
        sys.exit()

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