[dijkstra] 백준 11779 최소비용 구하기2(다익스트라 + 경로 노드)

기존 다익스트라 문제 + 거쳐가는 경로 노드를 구해야 하는 문제

 

import sys
import heapq
# 기존 다익스트라는 최소 거리만 계산
# 하지만 이 문제에서는 거쳐가는 노드를 출력해야한다. 
def dijkstra(start, end, n):
    distances = [float('inf')]*(n+1)
    distances[start]=0
    visit = [[] for _ in range(n+1)]
    visit[start].append(start)
    heap = [[0, start]]
    while heap:
        current_dist, current_idx = heapq.heappop(heap)
        if current_dist > distances[current_idx]:
            continue
        for next_idx, next_dist in graph[current_idx]:
            distance = current_dist + next_dist
            if distance < distances[next_idx]:
                distances[next_idx]=distance
                heapq.heappush(heap, [distance, next_idx])
                visit[next_idx]=[]
                visit[next_idx].extend(visit[current_idx])
                visit[next_idx].append(next_idx)
    print(distances[end])
    print(len(visit[end]))
    print(' '.join(map(str, visit[end])))

if __name__=="__main__":
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b, c = map(int, sys.stdin.readline().split())
        graph[a].append([b,c])
    start, end = map(int, sys.stdin.readline().split())
    dijkstra(start, end, n)