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

윤무무 2023. 2. 24. 12:21

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

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

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))