[Python] 백준11779 최소비용 구하기 2

01 Jul 2023 in Study on Algorithm

백준11779 최소비용 구하기 2 링크

문제

예제 입력

---

코드

import sys
import heapq

n = int(input())
m = int(input())

arr = [[] for _ in range(n+1)]
dist = [float("inf")] * (n+1)
# 이전 노드 저장
path = [0] * (n+1)
for _ in range(m):
    x, y, v = map(int, sys.stdin.readline().split())
    arr[x].append([y, v])

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

def dijkstra():
    q = []
    heapq.heappush(q, [0, st])
    dist[st] = 0

    while q:
        dst, node = heapq.heappop(q)

        # 기존 거리보다 멀다면
        if dist[node] < dst:
            continue

        # 노드와 연결된 인접노드 탐색
        for i in arr[node]:
            idx = i[0]
            cost = dst + i[1]
            if cost < dist[idx]:
                dist[idx] = cost
                path[idx] = node
                heapq.heappush(q, [cost, idx])

    ans = []
    tmp = end
    while tmp:
        ans.append(tmp)
        tmp = path[tmp]

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

dijkstra()

설명

파이썬을 통해서 사용자로부터 입력받아 다익스트라 알고리즘을 사용하여 최소비용 구하기 2를 구현했습니다.

---

결과