코딩테스트 준비/[백준]
[백준] 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)