[BOJ] 11657 - 타임머신 (Python)

 

 

아이디어

 

벨만-포드로 1번 도시에서 나머지 도시로 가는 가장 빠른 시간과 음의 사이클 여부를 확인한다.

 

 

풀이

 

두 도시 간 버스 노선이 여러 개일 수 있으므로 두 도시 간 이동 시간이 최소인 노선 정보를 저장한다.

 

import sys

input = sys.stdin.readline

INF = int(1e11)

def solution():
    N, M = map(int, input().split())
    graph = [dict() for _ in range(N+1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        graph[A][B] = min(graph[A].get(B, INF), C)
    D = [INF]*(N+1)
    D[1] = 0
    for _ in range(N-1):
        for idx in range(1, N+1):
            if D[idx] < INF:
                for i, c in graph[idx].items():
                    if D[idx]+c < D[i]:
                        D[i] = D[idx]+c
    _D = D[:]
    for idx in range(1, N+1):
        if _D[idx] < INF:
            for i, c in graph[idx].items():
                if _D[idx]+c < _D[i]:
                    _D[i] = _D[idx]+c
    if D == _D:
        for i in range(2, N+1):
            if D[i] < INF:
                print(D[i])
            else:
                print(-1)
    else:
        print(-1)

solution()