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

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

# 최소비용 구하기 2
import sys
import heapq
input = sys.stdin.readline
MAX = sys.maxsize

N, M = int(input()), int(input())
arr = [[]for _ in range(N+1)]
for _ in range(M):
    start, end, cost = map(int, input().split())
    arr[start].append((cost, end))


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    result[start] = 0
    while q:
        cost, city = heapq.heappop(q)
        if result[city] < cost:
            continue
        for ncost, ncity in arr[city]:
            if result[ncity] > cost + ncost:
                result[ncity] = cost + ncost
                heapq.heappush(q, (result[ncity], ncity))
                parent[ncity] = city


start, end = map(int, input().split())
result = [MAX] * (N+1)
parent = [i for i in range(N+1)]

dijkstra(start)
print(result[end])

path = []
temp = end
while True:
    path.append(temp)
    if temp == parent[temp]:
        break
    temp = parent[temp]
print(len(path))
path.reverse()
print(*path)

 

최단거리, 다익스트라

1. 인접리스트로 값을 입력받는다

2. 다익스트라 알고리즘을 실행하면서 parent리스트에 바로 윗부모를 기록해준다

3. 부모를 하나씩 거슬러 올라가면서 path리스트에 저장

4. 각각 출력 (path는 reverse해서 출력)