# 1916 최소비용 구하기 파이썬

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

import heapq
import sys
input = sys.stdin.readline 

n = int(input()) # 도시 
m = int(input()) # 버스 

graph = [ [] for _ in range(n+1)]
for i in range(m):
  s,e,c = map(int,input().split())
  graph[s].append((e,c)) # 도착, 비용 

s, e = map(int,input().split()) # 출발 도착 

def dij(start):
  q = []
  dist = [1e9]*(n+1)
  heapq.heappush(q, (0,start) )
  dist[start]=0

  while q : 
    d, now = heapq.heappop(q)

    if dist[now]< d : continue 

    for i in graph[now]:
      cost = d + i[1]
      if cost < dist[i[0]]:
        dist[i[0]] = cost 
        heapq.heappush(q, (cost,i[0]))

  return dist 

result = dij(s)
print(result[e])

 

기본 다익스트라 구현법 사용!