백준 11779. 최소비용 구하기 2

문제

접근 방법

거리 최소비용 구하기 -> 다익스트라로 접근

1. 그래프 초기화
2. 각 도시까지의 최소 비용을 저장하는 리스트를 만들고, 모든 비용을 INF로 초기화
3. 현재까지의 경로를 표시할 리스트 생성
4. 최소비용을 구하기 위한 heap(우선순위 큐) 생성하고 (현재까지 비용, 현재 도시)를 튜플로 가지도록 함
5. 다익스트라 실행

import sys
import heapq

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, E = map(int, sys.stdin.readline().split())

# 1. 그래프 생성
graph = [[] for _ in range(N + 1)]

for current, destination, cost in L:
    graph[current].append((destination, cost))

# 2. 각 도시까지의 최소 비용을 저장하는 리스트를 만들고, 모든 비용을 INF로 초기화
INF = float('inf')
dist = [INF] * (N + 1)

# 3. 현재까지의 경로를 표시할 리스트 생성
path = [-1] * (N + 1)
dist[S] = 0

# 4. 최소비용을 구하기 위한 heap(우선순위 큐) 생성하고 (현재까지 비용, 현재 도시)를 튜플로 가지도록 함
heap = [(0, S)]

# 5. 다익스트라 실행
while heap:
    current_cost, u = heapq.heappop(heap)

    if current_cost > dist[u]:
        continue

    for v, weight in graph[u]:
        new_cost = current_cost + weight
        if new_cost < dist[v]:
            dist[v] = new_cost
            path[v] = u
            heapq.heappush(heap, (new_cost, v))

# 경로를 산출해야 하니까 경로를 역으로 구함
route = []
current = E
while current != -1:
    route.append(current)
    current = path[current]
route.reverse()

print(dist[E])
print(len(route))
print(' '.join(map(str, route)))