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

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

11779번: 최소비용 구하기 2

다익스트라 알고리즘을 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면,

도시의 개수, 버스의 개수가 주어지고 버스들의 cost가 주어집니다. 이 때, 출발 도시에서 도착 도시까지의 최단 cost를 구하고, 이때의 path 정보 또한 구해야 하는 문제입니다.

 

<Solution>

기존의 다익스트라 알고리즘에 추가적으로 최단 거리로 가는 경로 또한 구해야 하는 문제입니다.

 

최단 cost는 인접 리스트와, heap을 이용한 fast dijkstra 알고리즘으로 구현이 가능합니다. 여기에 추가적으로 최단 경로에 대해 생각을 해보면, 다익스트라 알고리즘 진행 중 최단 경로가 갱신이 될 때, parent를 저장하는 형태로 구현 할 수 있습니다. 

https://stackoverflow.com/questions/28998597/how-to-save-shortest-path-in-dijkstra-algorithm

how to save shortest path in dijkstra algorithm

 

 

코드 진행중 아래의 한줄 코드를 추가함으로써 path정보를 저장할 수 있습니다. 

            # update parent
            parent[e_dst] = city

실제 구현은 아래와 같습니다.

import sys
import heapq

n = int(sys.stdin.readline()) # city
m = int(sys.stdin.readline()) # bus

array = [[] for _ in range(n+1)]

for _ in range(m):
    src, dst, cost = list(map(int, sys.stdin.readline().rstrip().split()))
    array[src].append([dst, cost])
    
f_src, f_dst = list(map(int, sys.stdin.readline().rstrip().split()))
### done with input ###
    
# dijkstra with path
parent = list(range(n+1)) # [0,1,2,...n]
distance = [int(2e9)]*(n+1)
distance[f_src] = 0
heap = [(0, f_src)]

while(heap):
    dist, city = heapq.heappop(heap)
    
    if distance[city] < dist:
        continue
    
    for e_dst, e_cost in array[city]:
        new_cost = dist + e_cost
        if distance[e_dst] > new_cost:
            # update parent
            parent[e_dst] = city
            distance[e_dst] = new_cost
            heapq.heappush(heap, (new_cost, e_dst))
        
# find path
path = []
tmp = f_dst
while(1):
    path.append(tmp)
    if tmp == parent[tmp]:
        break
    tmp = parent[tmp]
    
    
# print answers
print(distance[f_dst])
print(len(path))
print(' '.join(list(map(str, path[::-1]))))