minOS

백준 1719 택배 본문

Problem Solving/백준

백준 1719 택배

minOE 2025. 7. 6. 03:03
728x90

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()
728x90

'Problem Solving > 백준' 카테고리의 다른 글

백준 2670 연속부분최대곱  (0) 2025.07.15
백준 2578 빙고  (2) 2025.07.08
백준 5567 결혼식  (1) 2024.12.30
백준 2941 크로아티아 알파벳  (1) 2024.12.29
백준 15686 치킨 배달  (2) 2024.11.14