알고리즘: 백준 2211번 네트워크 복구 (feat.python)

 

2211번: 네트워크 복구

 

 

import sys
import heapq
read = sys.stdin.readline
INF = sys.maxsize
N, M = map(int, read().split())
net = {i: [] for i in range(1, N+1)}
for _ in range(M):
    A, B, C = map(int, read().split())
    net[A].append([C, B])
    net[B].append([C, A])

times =[[0, 0]]+ [[INF, 0] for _ in range(N)]
times[1] = [0, 0]
hq = []
heapq.heappush(hq, [0, 1])

while hq:
    cw, cn = heapq.heappop(hq)
    for nw, nn in net[cn]:
        next_weight = nw + cw
        if next_weight < times[nn][0]:
            times[nn] = [next_weight, cn]
            heapq.heappush(hq, [next_weight, nn])


def find_route():
    routes = []
    for i in range(2, len(times)):
        routes.append([i,times[i][1]])
    print(len(routes))
    for a, b in routes:
        print(a, b, end='')
        print()
        
        
find_route()