[Baekjoon] 최소비용 구하기 2(python)

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

문제 접근

다익스트라를 이용한 최단경로를 찾는 문제이다.

---

풀이 과정

다익스트라 알고리즘을 통해 start와 end 사이의 최단경로를 구하도록 한다.

경로도 같이 저장해야 하므로 dist배열을 갱신할 때 부모 노드를 parent배열에 저장하도록 한다.

---

정답 코드

"""
    백준 11779번 최소비용 구하기2
"""

import sys
import heapq


def dijkstra():

    dist[start] = 0
    queue = []
    heapq.heappush(queue, [dist[start], start])

    while queue:
        cost, node = heapq.heappop(queue)

        if dist[node] < cost:
            continue

        for next_node, next_cost in graph[node]:
            if cost + next_cost < dist[next_node]:
                dist[next_node] = cost + next_cost
                parents[next_node] = node
                heapq.heappush(queue, [cost + next_cost, next_node])

    return dist


n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

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


for _ in range(m):
    u, v, cost = list(map(int, sys.stdin.readline().split()))
    graph[u].append([v, cost])

start, end = list(map(int, sys.stdin.readline().split()))
dist = [int(1e9)] * (n + 1)
parents = [-1] * (n + 1)

dijkstra()

trace = [end]
while True:
    trace.append(parents[trace[-1]])
    if trace[-1] == start:
        break

print(dist[end])
print(len(trace))
print(*trace[::-1])