백준(baekjoon) 11657번: 타임 머신(골드 4, 파이썬 PYTHON) - 최단 경로

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

 

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

11657번: 타임머신

 

import sys

N,M=map(int,sys.stdin.readline().split())
info=[]
answer=[float('inf') for _ in range(N+1)]

for _ in range(M):
  info.append(list(map(int,sys.stdin.readline().split())))

answer[1]=0

for _ in range(N-1):
  for y in range(M):
    current=info[y][0]
    next=info[y][1]
    cost=info[y][2]
    if(answer[next]>answer[current]+cost):
      answer[next]=answer[current]+cost

flag=True

for x in range(M):
  current=info[x][0]
  next=info[x][1]
  cost=info[x][2]
  if(answer[next]>answer[current]+cost):
    flag=False
    break

if(flag==False):
  print(-1)
else:
  for x in range(2,N+1):
    if(answer[x]==float('inf')):
      print(-1)
    else:
      print(answer[x])

 

※ 최단 경로

 

 

● 버스 이동 시간이 음수인 경우가 있으므로 다익스트라가 아닌 벨만-포드 알고리즘을 활용한다.

 

● N개의 도시가 있으므로, 어느 도시로 이동하는데 사용하는 경로의 최대 수는 N-1개 이다. N-1번동안 주어진 모든 경로를 순회하며 각 도시까지 이동하는데 걸리는 최단 시간을 갱신해준다. 그 후 다시 한번 각 도시까지 이동하는데 걸리는 최단 시간을 확인하는데 만약 아직도 더 최단시간으로 갱신 되는 도시가 있다면 이 경우는 음의 순환이 발생하여 최단 시간을 특정 지을 수 없는 상황이다.

 

● 만약 음의 순환이 발생한 경우는 -1을 출력해주고, 음의 순환이 없다면 2번부터 N번 도시까지 가는데 걸리는 최단 시간을 차례대로 출력해준다. 만약 특정 도시까지 가는 경로가 없다면 -1을 출력해준다.

 

 

 

 

♣ 벨만-포드 알고리즘

-> https://velog.io/@kimdukbae/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Bellman-Ford-Algorithm

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)