[백준] 1719번 택배 - 파이썬/다익스트라

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

import heapq

n,m = map(int,input().split())

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

INF = int(1e9)


for i in range(m):

    a,b,c = map(int,input().split())

    graph[a].append((b,c))
    graph[b].append((a, c))


def dij(start):
    q = []
    distance = [INF] * (n + 1)
    distance[0] = 0
    distance[start] = 0
    root = [ [] for _ in range(n+1) ]

    heapq.heappush(q,(0,start,[start]))

    while q:

        dist,now,temt_route = heapq.heappop(q)

        if dist>distance[now]:
            continue

        for i in graph[now]:

            cost = dist + i[1]

            if cost<distance[i[0]]:
                distance[i[0]] = cost
                new_route = temt_route + [i[0]]
                heapq.heappush(q,(cost,i[0],new_route))
                root[i[0]] = new_route

    for i in root[1:]:
        if i:
            print(i[1],end=' ')
        else:
            print('-',end=' ')

    print()

for i in range(1,n+1):
    dij(i)

다른 문제처럼 최단거리를 묻는 것이 아닌 최단 거리까지의 경로를 묻는 문제이다.

힙큐의 원소를 (거리, 노드,지금까지 경로) 로 넣고 다익스트라 알고리즘을 실행시켜 최단경로를 구할 수 있다.