백준 1719 택배

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

 

import sys
import heapq
INF = sys.maxsize
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b,time = map(int,input().split())
    graph[a].append((time,b))
    graph[b].append((time,a))



def dijkstra(start):
    dist[start] =0
    heapq.heappush(pq,(0,start))
    
    while pq :
        min_dist,min_node = heapq.heappop(pq)
        
        if dist[min_node] != min_dist:
            continue
        
        for target_dist,target_node in graph[min_node]:
            new_dist = min_dist+target_dist
            if new_dist < dist[target_node]:
                dist[target_node] = new_dist
                heapq.heappush(pq,(new_dist,target_node))
                road[target_node] = min_node
                                        
    
    return road



ans =[]
for i in range(1,n+1):
    dist = [INF for _ in range(n+1)]
    road = [0 for _ in range(n+1)]
    pq =[]
    ans.append(dijkstra(i))
for j in range(1,n+1):
    for i in range(n):
        if ans[i][j] == 0 :
            print("-",end=" ")
        else:
            print(ans[i][j],end=" ")
    print()