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

문제

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

11657번: 타임머신

 

풀이 및 소스코드

벨만포드 알고리즘으로 푸는 문제이다.

어려워 ...

다익스트라와의 차이점은 매 반복마다 모든 간선을 확인한다는 것

다익스트라는 방문하지 않는 노드 중에서 최단 거리가 가장 가까운 노드만을 방문

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

n, m = map(int, input().split())
edges = [] #간선에 대한 정보 담는 리스트
dist = [INF]*(n+1)

for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((u,v,w))

def bf(start):
    dist[start] = 0
    for i in range(n):
        for j in range(m):
            node = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if dist[node]!=INF and dist[next_node]>cost+dist[node]:
                dist[next_node] = dist[node]+cost
                if i == n-1: #정점의 끝인데 계속 값이 갱신되면 음수 순환 존재.
                    return True
    return False

n_c = bf(1)

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