백준_1916_최소비용구하기/Using Python 파이썬

문제

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

1916번: 최소비용 구하기

 

About Problem

문제의 핵심은 저 두줄이다. 간선의 정보를 주고 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 것이다.

간선의 비용이 양수이며 다르고 최소 비용을 구하는 알고리즘은  다익스트라 알고리즘이다.

 

간선의 최단경로를 구하는 알고리즘은 다음과 같다

출처 메자곰(https://technote-mezza.tistory.com/107)

 

Code

코드 설명은 코드 주석으로 적었다.

from sys import stdin
import heapq

# input 받기
N = int(stdin.readline())
M = int(stdin.readline())

# index를 이용해서 간선의 위치를 파악 할수 있게 해주는 list만들기
lst = [[] for _ in range(N+1)]

# 최소비용을 찾는거기 때문에 각 위치까지 도착할 비용을 최대로 잡기
inf = int(1e9)
cost_lst = [inf] * (N+1)

# 출발 index에 [도착, cost]를 append 하기
for i in range(M):
    S, E, C = list(map(int, stdin.readline().split()))
    lst[S].append([E, C])

# 출발지, 도착지 받아오기
s, e = map(int, stdin.readline().split())

# 출발지는 비용이 0이므로 0으로 만들어주고, Q에 (비용, 출발지) 리스트로 넣기
cost_lst[s] = 0
Q = [(0, s)]

# 다익스트라
while Q:
    # 현 위치까지 오는데 비용, 현 위치
    c, n = heapq.heappop(Q)
    # heapq를 쓰기 때문에 이전에 방문했던 곳이면 pass
    if cost_lst[n] == c:
        # lst안에 들어있는 갈수있는곳과 cost 파악하기
        for go, cost in lst[n]:
            now_cost = cost_lst[n] + cost
            # 갈곳의 비용이 계산한 비용보다 클 때에만 가게하기
            if cost_lst[go] > now_cost:
                cost_lst[go] = now_cost
                heapq.heappush(Q, (now_cost, go))
print(cost_lst[e])