[백준/Python/그래프, 벨만-포드] 11657 - 타임머신

1. 문제 링크

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

11657번: 타임머신

 

2. 문제 해석

• input:
  • 도시의 개수 N
  • 버스 노선의 개수 M
  • M개의 줄에 각 버스 노선의 정보 A (시작도시), B (도착도시), C (이동시간)
    • C == 0, 순간이동
    • C < 0, 타임머신으로 시간 되돌아감
• output:
  • 1번 도시에서 출발해서 무한히 과거로 갈 수 있으면, print("-1")
  • OR N-1번 출력
    • 각 줄에는 1번 출발 후 N번째 도시에 도착하는 가장 빠른 시간 C 출력
    • N번째 도시로 가는 경로 없다면 print("-1)
• 최단 거리 출력과 같음

 

3. 발생한 문제 및 문제 해결

• Index Error

 

4. 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(M)]


def BellmanFord(start):
    distance = [float('inf') for _ in range(N+1)]
    flag = [False for _ in range(N+1)]
    distance[start] = 0

    for i in range(M):
        for [A, B, C] in graph:
            if distance[A] != float("inf") and distance[A] + C < distance[B]:
                distance[B] = distance[A] + C

    for [A, B, C] in graph:
        if distance[A] + C < distance[B]:
            print(-1)
            exit()

    for i in range(2, N+1):
        if distance[i] == float('inf'):
            print(-1)
        else:
            print(distance[i])


BellmanFord(1)

 

5. 참고자료

https://codingexplore.tistory.com/58

https://velog.io/@younge/Python-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98