[백준] 11779 최소비용 구하기 2 (파이썬 python)

 

 

문제 링크

 

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

11779번: 최소비용 구하기 2

 

 

 

문제 풀이

 

 

최소비용 구하기 문제가 최소 비용만을 출력하는 것이었다면,

이 문제에서는 최소 비용으로 도착점에 가는 루트에 있는 모든 노드를 출력해야 합니다.

이를 위해, 이동 경로에 있는 노드들을 저장할 route라는 2차원 배열을 선언하였습니다.

route배열에서 현재 노드에 대한 인덱스값은

현재 노드까지 이동하기 위한 최소 비용 루트에 포함된 노드 배열입니다.

 

distance에 비용을 갱신하는 기존에 존재했던 로직 위치에 루트에 대한 로직도 추가해줍니다.

route 배열에서 다음 이동할 노드 인덱스에 대한 값을

지금까지 이동한 루트 내 노드 배열에 다음 이동할 노드를 더해 갱신시켜줍니다.

 

for node, weight in graph[now]:
            weight += dist
            if weight < distance[node]:
                distance[node] = weight
                route[node] = nodes + [node]
                heapq.heappush(q, (weight, node, nodes + [node]))

 

 

전체 코드

 

import heapq, sys
input = sys.stdin.readline

def dijkstra(start):
    q = []
    distance[start] = 0
    heapq.heappush(q, (0, start, [start]))
    while q:
        dist, now, nodes = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for node, weight in graph[now]:
            weight += dist
            if weight < distance[node]:
                distance[node] = weight
                route[node] = nodes + [node]
                heapq.heappush(q, (weight, node, nodes + [node]))

n = int(input())
m = int(input())
graph = [[] for _ in range(n + 1)]
distance = [1e9] * (n + 1)
route = [[] for _ in range(n + 1)]
for _ in range(m):
    s, e, w = map(int, input().split())
    graph[s].append((e, w))
start, end = map(int, input().split())
dijkstra(start)

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