1916 최소비용 구하기(벨만포드 실패)

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

#dijkstra algorithm

1916번: 최소비용 구하기

#bellman-Ford's algorithm

 

모든 edge를 최대 혹은 최소 값으로 설정해놓은 후 시작 edge를 0으로 하고 그것을 기준으로 모든 edge의 값을 재설정

 

해주는 알고리즘 다익스트라와 달리 음수가 가중치일때도 사용 가능

 

예를들어

 

1 2 3

2 3 5

1 3 7

 

이렇게 있으면 다익스트라는 1 2 2 3 각각의 최선의 경로로 가고 벨만포드 역시 그러겠지만

 

1 2 3

2 3 5

3 4 -8

2 4 1

이런식으로 있으면 다익스트라에서는 2를 시작점으로 가질때 최적의 답이 2 4 1 이기때문에 답이 0이 아닌 4로 마무리 되게 됩니다. 벨만포드는 이를 방지하기 위해 연관되는 모든 경로를 다 거치게 되는 것입니다. 고로 벨만포드를 이용하면 0으로 마무리 됩니다.

 

### 이문제에서 벨만포드를 사용하면 시간초과가 발생하여 다익스트라로 변경하였다.

 

 

#1916 최소비용 구하기
import sys
import heapq

input=sys.stdin.readline
push=heapq.heappush
pop=heapq.heappop

#sys 최댓값사용과 스탠다드 인풋을 위해 heapq 제일 작은 비용을 빼내기 위해서

n=int(input())

m=int(input())

cost=[[] for i in range(n+1)]

#비용 리스트 작성

for i in range(m):

s,a,c=map(int,input().split())

cost[s].append([a,c])

#비용 리스트를 시작도시를 인덱스로 갖은 [도착도시, 비용] 의 리스트만들기

start,end=map(int,input().split())

time_table=[sys.maxsize]*(n+1)

#각 인덱스값 최대로 하여 최소비용을 구할 수 있도록함

time_table[start]=0

heap=[(0,start)]

#[비용,시작도시]

while heap:

money,now_city=pop(heap)
#now_city로 오기까지 money가 들었다.
if money >= time_table[end]:
break

#경로로 가는건데 만약 도착하기 전에 이미 end를 넘어버리면 함수를 멈춘다. 앞으로의 경로에 음수가 없다는 가정하에 #설정된 조건

for next_city,expense in cost[now_city]:

expense1=expense+money

if time_table[next_city] > expense1:

time_table[next_city]=expense1

push(heap,(expense1,next_city))

print(time_table[end])

 

#지금의 도시부터 다음도시로 가는 경로와 비용을 살펴본 후 지금도시로 오는 비용+다음도시로 가는 비용이 현재 설정된 그 도시로 가는 비용(time_table[next_city])보다 작을경우 최소비용이므로 갱신한다. 갱신 되었으므로 여기서 이 다음도시에서 최종도착도시로 가기까지의 경로를 탐색하기위해 heap에 넣어준다.