[백준] 11657번: 타임머신

문제

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

풀이

벨만포드 알고리즘을 활용한 문제 풀이

벨만포드 알고리즘의 시간복잡도는 O(VE) 이다
도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이기 때문에
시간 복잡도에서 문제가 생기지 않는다.

import sys

INF = sys.maxsize
sys.stdin = open("data.txt", "r")

N, M = map(int, input().rstrip().split(" "))
graph = []
for _ in range(M):
    graph.append(list(map(int, input().rstrip().split(" "))))

def bellmanFord(start, graph, N):
    distances = [INF] * (N + 1)
    distances[start] = 0
    for _ in range(N-1):
        for mid, end, weight in graph:
            if distances[mid] != INF and distances[end] > distances[mid] + weight:
                distances[end] = distances[mid] + weight

    for mid, end, weight in graph:
        if distances[mid] != INF and distances[end] > distances[mid] + weight:
            return -1

    return distances

def solution(N, M, graph):
    distances = bellmanFord(1, graph, N)
    if distances == -1:
        print(-1)
    else:
        for i in range(2, len(distances)):
            if distances[i] == INF:
                print(-1)
            else:
                print(distances[i])
    return

solution(N, M, graph)