[백준] 11657 파이썬

문제

---

• 백준 11657 (골드 4)

백준 11657

n개의 도시와 m개의 도시 이동 가중치가 주어질 때, 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 문제였다.
여기서 문제의 조건은 음수 가중치가 주어질 수 있고, 시간을 무한히 돌릴 수 있다면 -1을 출력하고 종료하는 것이였다.

내 코드

---

음수 가중치도 주어진다는 점에서 벨만 포드 알고리즘이 생각나서 해당 알고리즘을 통해서 구현해보았다.
벨만 포드 알고리즘을 수행하면서 dist 리스트를 업데이트 하면서 각 도시로의 이동 가중치를 구해주었다.
이때 무한한 음수 순환이 존재한다면 -1을 출력하고 종료하도록 해주었다.

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
bus = [list(map(int, input().split())) for _ in range(m)]
dist = [INF] * (n + 1)

def bellman_ford(st):
    dist[st] = 0
    for i in range(n):
        for j in range(m):
            current, next, edge_cost = bus[j]
            if dist[current] != INF and dist[next] > dist[current] + edge_cost:
                dist[next] = dist[current] + edge_cost
                if i == n - 1:
                    print(-1)
                    exit()
                
bellman_ford(1)

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