11657 타임머신 정리

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

#bellman ford algorithm

11657번: 타임머신

#bellman ford algorithm

 

간단히 말해서 다익스트라와 비슷한데 다른점은 start와 직접적으로 관련되지 않은 vertex까지 탐색함으로써 음수가 나

 

와서 start와 직접적으로 관련되있지 않더라도 연결되면 최소비용이 나오는 상황이 되었을때 사용되는 알고리즘이다. 어

 

떻게 되면 브루트포스와 비슷하다. 이유는 모든 간선을 모두 돌며 조건은 초기 설정한 cost[start]=0 제외한 n-1번 모든

 

간선을 최소비용을 찾으면서 도는 것이기 때문에 좀 무식한 알고리즘으로 볼 수있다. 따라서 시간역시 다익스트라가 훨

 

씬 빠르다. 하지만 음수가 가중치인 상황에서 쓸 수 있다는 점이 매력적인 알고리즘이다.

 

#code

#11657 타임머신 벨만포드
import sys

input=sys.stdin.readline

 

def bellmanford(start):

 

now_cost=[float("inf") for i in range(n+1)]

#각 도시의 최소비용을 담을 리스트

now_cost[start]=0

#시작도시는 현재 위치이기때문에 비용이 없음

for _ in range(n-1):

#시작도시를 제외한 모든 도시의 개수만큼 탐색 이것을 넘으면 모든 도시의 개수를 넘어서 돌릴게 있다는 이야기 이므로 순환되고있다는 걸 알 수 있다.

 

for start_city,end_city,cost in bus_num:

#모든 간선을 비교한다.

 

if now_cost[start_city]!=float("inf") and now_cost[start_city]+cost < now_cost[end_city]:

now_cost[end_city] = cost+now_cost[start_city]

#만약 시작도시를 인덱스로 갖는 값이 초기값이거나 최소비용이 이 간선을 사용한것보다 작으면 돌지 않고 둘다 해당되#면 갱신한다.

 

for start_city,end_city,cost in bus_num:

if now_cost[start_city]!=float("inf") and now_cost[start_city] + cost < now_cost[end_city]:

return 0
#순환 되는지 확인

 

return now_cost
#갱신된 리스트 리턴

n,m=map(int,input().split())

bus_num=[list(map(int,input().split())) for i in range(m)]

start=1

now_cost=bellmanford(start)

if now_cost!=0:

# 순환되지 않을때

for i in range(2,n+1):

print(now_cost[i] if now_cost[i]!=float("inf") else -1)

#시작도시인 1을 제외하고 인덱스 편할려고 더했던 0도 제외하고 나머지 출력 만약 리스트가 아직 초기값이면 -1 출력

else:

print(-1)

#순환되면 -1 출력

 

#1916 최소비용 구하기 풀다가 11657 벨만포드까지 왔다. 음수가 더해지면서 다익스트라를 못 사용한다고 할때 사용할 #알고리즘이다.