BaekJoon 11779번 : 최소비용 구하기 2 (python)

BaekJoon 11779번 : 최소비용 구하기 2 (G3 36.683%)

최소비용 구하기 2

다익스트라 알고리즘을 이용한 가중치가 다른 노드 사이에서 최소 비용을 구하는 문제에 역추적 조건이 더해진 문제이다.

• 기본적인 다익스트라 알고리즘을 구현한다. 다익스트라 알고리즘은 heapq 자료구조를 이용해서 문제를 풀게된다. heapq 자료구조를 이용해서 가장 가까운, 가장 짧은 거리의 노드를 먼저 방문하는 방식을 이용하게 된다.
• 기본적인 다익스트라 알고리즘에서 역추적을 하기 위해 distance가 업데이트 되는 시점에 position[next]에 현재 x를 넣어줌으로써 이전의 위치 index값을 저장하게 된다.
• 역추적을 할 때는 position의 end값부터 시작해서 start index에 닿을 때 까지 진행하게 된다.

import sys,heapq
input = sys.stdin.readline

def dijkstra(start) :
    q = list()
    heapq.heappush(q,(start,0))
    distance[start] = 0
    while q :
        x, count = heapq.heappop(q)

        if distance[x] < count :
            continue
        for i in maps[x] :
            cost = count + i[1]
            next = i[0]
            if distance[next] > cost :
                distance[next] = cost
                position[next] = x
                heapq.heappush(q,(next,cost))

n = int(input())
m = int(input())
maps = [[]*(n+1) for _ in range(n+1)]
distance = [float('inf')]*(n+1)
position = [-1]*(n+1)
for _ in range(m) :
    a, b, c = map(int,input().split())
    maps[a].append((b,c))
start, end = list(map(int,input().split()))

dijkstra(start)
print(distance[end])
result = list()
while end != -1 :
    result.append(end)
    end = position[end]
print(len(result))
print(*result[::-1])