백준 1753 최단경로

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

 

 이 문제는 간편하게 시작지점에서 다른 모든 지점으로의 최소경로의 길이를 구하는 문제이다. 

 

 이 문제는 그냥 데이크스트라 알고리즘을 충실히 구현하면 풀린다. 데이크스트라 알고리즘에 관해서는 https://jangbearbio.tistory.com/102 이 글에서 자세히 다뤘으므로, 이 글에서는 자세히는 다루지 않겠다. 

 

이 문제를 풀면서, 필자는 무의식적으로 데이크스트라 알고리즘을 구현할 때 큐를 말그대로 덱으로 하여, bfs의 큐처럼 사용했지만, 무게를 기준으로 최솟값이 항상 앞으로 튀어나오게 하는 heapq 자료형을 사용하는 것이 시간적이나 알고리즘적으로 더 낫다는 것을 기억하게 되었다. 가장 작은 무게가 먼저 나오기에, 같은 경로 상의 더 큰 무게의 엣지는 자연스레 무시하게 된다. 그렇기에 heap에 무게와 노드가 동시에 들어가며 탐색하게 된다.

 

import sys
input = sys.stdin.readline
import math
import heapq

def Dijkstra():
    Ds=[math.inf for _ in range(V+1)]
    Ds[start]=0
    heap=[]
    heapq.heappush(heap,[0,start])

    while heap:
        now_d,now_n = heapq.heappop(heap)
        if Ds[now_n] < now_d:
            continue
        for next_d,next_n in Es[now_n]:
            sum_d = now_d+next_d
            if sum_d >= Ds[next_n]:
                continue
            Ds[next_n] = sum_d
            heapq.heappush(heap,[sum_d,next_n])
    
    return Ds


V,E = map(int,input().rstrip().split())
start = int(input().rstrip())

Es=[[] for _ in range(V+1)]

for _ in range(E):
    n1,n2,w = map(int,input().rstrip().split())
    Es[n1].append([w,n2])

for i in Dijkstra()[1:]:
    if i==math.inf:
        print('INF')
    else:
        print(i)