문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

# 1753
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

import heapq
v, e = map(int, input().split())
graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)

start = int(input())

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
def dijkstra(start):
    q = []
    heapq.heappush(q, (0 ,start))
    distance[start] = 0
    while q:
        dist, node = heapq.heappop(q)
        if distance[node] < dist:
            continue
        for j in graph[node]:
            cost = dist + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost
                heapq.heappush(q, (cost, j[0]))
                
dijkstra(start)

for i in range(1, v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

우선순위 큐를 사용하는 과정에서 (노드, 거리) 를 사용하면 (거리, 노드)를 사용할 때 보다 많은 계산을 하게 된다.

백준 1753 최단경로