[백준]1916번 최소비용 구하기 -python 파이썬

문제

 

 

 

이 문제는 비용을 거리로 생각한다면 전형적인 다익스트라 알고리즘 문제이다.

 

 

그렇기 때문에 heap 을 사용하여 문제를 해결해주었다.

 

나의 코드

 

import sys
import heapq

input = sys.stdin.readline

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]

for i in range(m):
    s,e,p = map(int,input().split())
    graph[s].append([e,p])

start , dest = map(int,input().split())
#각 도시별 필요한 비용을 담는 리스트
costs = [1e9 for _ in range(n+1)]
heap = []
#시작점 추가
costs[start] = 0
heapq.heappush(heap,[0,start])

while(heap):
    #현재 비용과 위치 
    cur_p, cur_v = heapq.heappop(heap)
    #costs 리스트에 담긴 현재위치의 비용이 더 작다면 컨티뉴
    if costs[cur_v] < cur_p:
        continue
    #현재 위치에서 갈 수 있는 목적지의 비용 업데이트
    for  next_v, next_p in graph[cur_v]:
        sum_c = cur_p + next_p 
        if sum_c < costs[next_v]:
            costs[next_v] = sum_c
            heapq.heappush(heap,[sum_c, next_v])
print(costs[dest])

 

 

 

 

graph의 형태로 목적지와 비용을 담아주고 이를 heap 을 이용해 해결해주는 방법을 생각하는 것이 가장 중요했던 문제였다.