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

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

start, end = map(int, input().split())

def dijkstra(start ,end):
    distance = [INF] * (n+1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, dest = heapq.heappop(q)
        if distance[dest] < cost:
            continue
        for d, c in graph[dest]:
            tmp = c + cost
            if distance[d] > tmp:
                distance[d] = tmp
                heapq.heappush(q, (tmp, d))

    return distance[end]

print(dijkstra(start, end))

백준에서 sys.stdin.readline을 해주지 않으면 시간초과가 난다.

아주 기본적인 다익스트라 알고리즘.