[Python] 백준1916 최소비용 구하기

22 May 2023 in Study on Algorithm

백준1916 최소비용 구하기 링크

문제

예제 입력

---

코드

import sys
import heapq

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

arr = [[] for _ in range(n+1)]
dist = [float("inf")] * (n+1)
for _ in range(m):
    x, y, v = map(int, sys.stdin.readline().split())
    arr[x].append([y, v])

a, b = map(int , input().split())
def dijkstra():
    q = []
    heapq.heappush(q, [0, a])
    dist[a] = 0

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

        if dist[now] < dst:
            continue
        for i in arr[now]:
            cost = dst + i[1]
            idx = i[0]
            if cost < dist[idx]:
                dist[idx] = cost
                heapq.heappush(q, [cost, idx])

dijkstra()
print(dist[b])

설명

파이썬을 통해서 사용자로부터 입력받아 다익스트라알고리즘을 사용하여 최소비용 구하기를 구현했습니다.

---

결과