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

문제

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

1916번: 최소비용 구하기

 

코드

import heapq
import sys

INF = sys.maxsize
input = sys.stdin.readline
n = int(input())
m = int(input())

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

for i in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((c,b))

start, end = map(int, input().split())
queue = []

def dijkstra(start):
    heapq.heappush(queue, (0, start))
    while queue:
        wei, now = heapq.heappop(queue)
        if distance[now] < wei:
            continue
        for w, next in graph[now]:
            next_wei = w + wei
            if distance[next] > next_wei:
                distance[next] = next_wei
                heapq.heappush(queue, (next_wei, next))
dijkstra(start)
print(distance[end])

가중치가 주어지고 최소비용을 구하는 문제로 다익스트라를 사용하여 풀었다.

 

시작 지점에서 다른 정점까지 갈 수 있는 최소비용으로 초기화 해준다.