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

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

11779번: 최소비용 구하기 2

백준 1916번 최소비용 구하기 문제의 변형으로 경로를 추가적으로 구해주면 된다.

distance에 각 노드로 갈 수 있는 최소 비용뿐만 아니라 각 노드에서 이전에 방문한 노드를 추가적으로 넣어줘서 해결을 하였다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())
graph = [[] for i in range(n + 1)]
distance = [[INF,[]] for _ in range(n+1)]

for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))

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

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start][0] = 0
    distance[start][1] = start

    while q:
        dist, now = heapq.heappop(q)
        if distance[now][0] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]][0]:
                distance[i[0]][0] = cost
                distance[i[0]][1] = now
                heapq.heappush(q,(cost,i[0]))

dijkstra(start)
tmp = end
ans = [str(end)]
while True:
    if distance[tmp][0] == 0:
        break
    else:
        ans.append(str(distance[tmp][1]))
        tmp = distance[tmp][1]

print(distance[end][0])
print(len(ans))
print(' '.join(ans[::-1]))

#output
4
3
1 4 5

해당 코드를 주어진 예제에 적용을 해보면 1 4 5라는 경로가 나와 문제의 예제 출력인 1 3 5와는 다르지만 가능한 모든 경로 중 하나만 출력하면 됨으로 정답으로 처리가 된다.