11779: 최소비용 구하기 2

풀이 시간

• 29m

구현 방식

• 이 문제는 dijkstra 알고리즘을 이용하여 최단 거리를 구하는 것뿐만 아니라, 최단 '경로'를 구해야하는 문제였다

• "1916: 최소비용 구하기" 문제에선 costs에 거리만 저장해주었지만, 원소를 하나 더 추가해서 부모 노드도 저장해주어야한다
  -> E부터 시작하여 S가 나오기 전까지 부모노드를 따라서 최단경로를 탐색해주면 됨

코드

import sys
import heapq


def dijstra(start):
    costs[start][0] = 0
    heap = []
    heapq.heappush(heap, [costs[start][0], start])

    while heap:
        curr_cost, curr = heapq.heappop(heap)
        if costs[curr][0] < curr_cost: continue
        for next, next_cost in graph[curr]:
            cost = curr_cost + next_cost
            if costs[next][0] > cost:
                costs[next][0] = cost
                costs[next][1] = curr #부모노드 저장
                heapq.heappush(heap, [costs[next][0], next])


N = int(sys.stdin.readline()[:-1]); M = int(sys.stdin.readline()[:-1])
graph = dict()
for n in range(1, N+1):
    graph[n] = []
for m in range(M):
    S, E, cost = map(int, sys.stdin.readline()[:-1].split())
    graph[S].append((E, cost))

costs = dict()
for n in range(1, N+1):
    costs[n] = [int(10e9), n]

S, E = map(int, sys.stdin.readline()[:-1].split())
dijstra(S)
print(costs[E][0])

path = []; dest = E
while True:
    pre_node = costs[dest][1]
    if pre_node == S:
        break
    path.append(pre_node)
    dest = pre_node

print(len(path) + 2)
print(S, end=" ")
for i in range(len(path)-1, -1, -1):
    print(path[i], end=" ")
print(E, end=" ")
print()

결과