# BOJ - 11779 - 최소비용 구하기 2

Updated:

```
import sys
from heapq import heappush, heappop
def Dijkstra(start, end, graph, V):
heap = []
distance = [1e9] * (V +1)
distance[start] = 0
heappush(heap, (0, start))
ret = [0 for _ in range(V+1)]
while heap:
weight, location = heappop(heap)
if distance[location] < weight:
continue
for l, w in graph[location]:
w += weight
if w < distance[l]:
distance[l] = w
heappush(heap, (w, l))
ret[l]=location
arr = []
idx = end
cnt = 0
while ret[idx] != 0:
arr.append(idx)
idx = ret[idx]
arr.append(idx)
arr.reverse()
print(distance[end])
print(len(arr))
print(*arr)
def solution():
N = int(input())
M = int(input())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
u, v, w = map(int, sys.stdin.readline().split())
graph[u].append([v, w])
start, end = map(int, sys.stdin.readline().split())
Dijkstra(start, end, graph, N)
solution()
```

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

## Leave a comment