[백준] 2211번 네트워크 복구

bled 2021. 7. 16. 00:16

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

2211번: 네트워크 복구

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다

www.acmicpc.net

import sys, heapq

input = sys.stdin.readline
n, m = map(int, input().split())
INF = sys.maxsize


def dijk(start):
    d = [INF] * n
    d[start] = 0
    q = []
    heapq.heappush(q, [d[start], start])

    while q:

        dist, cur = heapq.heappop(q)
        if d[cur] < dist:
            continue
        for next, cost in graph[cur]:
            c = cost + dist
            if c < d[next]:
                p[next] = cur
                d[next] = c
                heapq.heappush(q, [d[next], next])

p = [-1] * n
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a - 1].append([b - 1, c])
    graph[b - 1].append([a - 1, c])



dijk(0)
print(n - 1)

for i in range(1, n):
    print(i + 1, p[i]+1)