[python]11657번 타임머신,벨만 포드 알고리즘

우선순위 큐를 사용하지 않기에, 입력 제한 값이 상당히 낮았다.(도시 갯수 500개 이하, 버스 노선 6000개 이하)

최악의 연산도 300백만경우이기에 1초 안에 계산 가능했던거 같다.

 

 

import sys
city,bus = map(int,input().split())
graph = []
for i in range(bus):
    fst,scd,thd = map(int,input().split())
    graph.append((fst,scd,thd))
distance = [1e9 for i in range(city+1)]
def bm(start):
    distance[start] = 0
    for i in range(city):   #노드 수 만큼 그래프 순회하기
        for j in range(bus): #간선들 순회
            curs,cure,curl = graph[j]
            if distance[curs]!=1e9 and distance[cure]>distance[curs]+curl:  #도달 가능한 노드에 있는지 확인 작업 필수
                distance[cure]=distance[curs]+curl
                if i == city-1: #끊임없이 값이 갱신된다면 싸이클에 빠진것
                    return True
    return False
if bm(1):  #무한 싸이클에 빠졌다.
    print(-1)
else:
    for i in range(2,city+1):
        if distance[i]!=1e9: #도달 가능할 시
            print(distance[i])
        else: #도달 불가능할 시
            print(-1)