# BOJ - 1719 - 택배

Updated:

```
import sys
from heapq import heappush, heappop
def Dijkstra(K, graph, V):
heap = []
distance = [1e9] * (V + 1)
distance[K] = 0
cource = [0] * (V + 1)
heappush(heap, (0, K))
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
cource[l] = location
heappush(heap, (w, l))
return cource
def solution():
V, E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
u, v, w = map(int, sys.stdin.readline().split())
graph[u].append([v, w])
graph[v].append([u, w])
for idx in range(1, V+1):
course = Dijkstra(idx, graph, V)
ret = ['-'] * (V + 1)
for jdx in range(1, V+1):
if idx == jdx:
continue
checkIndex = jdx
while 1:
kdx = course[checkIndex]
if kdx == idx:
ret[jdx] = checkIndex
break
checkIndex = kdx
for i in range(1, V+1):
print(ret[i], end=' ')
print()
solution()
```

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

## Leave a comment