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

문제링크 : 최소비용 구하기2

최소비용구하기=>다익스트라

import sys
import heapq

inf=sys.maxsize
input=sys.stdin.readline
n=int(input())
graph=[[] for _ in range(n+1)]
m=int(input())
for i in range(m):
    a,b,w=map(int, input().split())
    graph[a].append((b,w))
start,end=map(int, input().split())
distance=[inf for _ in range(n+1)]
path=[[] for _ in range(n+1)]
path[start].append(start)
heap=[]
heapq.heappush(heap, (start,0))
while heap:
    now,wei=heapq.heappop(heap)
    if wei>distance[now]:
        continue
    if now==start:
        distance[now]=0
    for next,next_cost in graph[now]:
        path_cost=next_cost+wei
        if path_cost<distance[next]:
            distance[next]=path_cost
            heapq.heappush(heap,(next,path_cost))
            path[next]=[]
            for p in path[now]:
                path[next].append(p)
            path[next].append(next)

print(distance[end])
print(len(path[end]))
print(' '.join(map(str,path[end])))

이 문제의 경우 경로까지 출력을 해야해서 path라는 배열을 만들어서 경로를 저장하는게 포인트다!
저장된 경로의 비용보다 더 작은 비용이 나타나면 path를 리셋하고 새로운 경로를 저장한다.