[백준] 1916번 최소비용 구하기(python)

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

1916번: 최소비용 구하기

 

1. 난이도 골드5 (🥇)

 

2. 내가 작성한 코드

 

한 지점에서 한 지점까지의 최단경로 + 가중치가 모두 음이 아님을 만족하기 때문에

 

다익스트라 알고리즘을 이용하면 된다.

 

import heapq
import sys

n = int(input().rstrip()) #도시의 개수
m = int(input().rstrip()) #버스의 개수

INF = int(1e9)
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for i in range(m):
  a,b,c = map(int, input().rstrip().split())
  graph[a].append((b,c)) #b는 도착도시, c는 가중치

def short(a,b):
  q = []
  heapq.heappush(q,(0,a))
  distance[a] = 0

  while q:

    dist,now = heapq.heappop(q)

    if distance[now] < dist:
      continue

    for i in graph[now]:
      cost = dist + i[1]

      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q,(cost,i[0]))

  return distance[b]

start, end = map(int, input().rstrip().split())
print(short(start,end))