[테스트케이스 추가] 백준 2211번: 네트워크 복구 (python, 파이썬)

1. 문제: 백준 2211번: 네트워크 복구

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

2211번: 네트워크 복구

 

 

 

2. 풀이

다익스트라를 하면서 heap에 push할 때 prev 어레이에 현재 값과 앞(index)으로 연결될 값(value)을 입력해준다.

 

 

 

3. 구현

import sys
import math
import heapq

# sys.stdin = open('input.txt')

n,m = map(int, sys.stdin.readline().split())
cnt = m

gph=[[] for  _ in range(n+2)]
prev = [ 0 for _ in range(n+2)]

def dijk(node):
  dist=[math.inf for _ in range(n+2)]
  edges=[]
  dist[node]=0
  heapq.heappush(edges, (dist[node], node))
  while edges:
    cost,pos = heapq.heappop(edges)
    if dist[pos]<cost:
      continue
    for p,c in gph[pos]:
      c+=cost
      if dist[p]>c:
        dist[p]=c
        prev[p] = pos
        heapq.heappush(edges, (c,p))
  return dist

while cnt:
  cnt-=1
  a,b,c = map(int, sys.stdin.readline().split())
  gph[a].append((b,c))
  gph[b].append((a,c))

# print(dijk(1))
dijk(1)
cnt=0
for iter in prev:
  if iter!=0:
    cnt+=1
print(cnt)

for idx, item in enumerate(prev):
  if item!=0:
    print(idx, prev[idx])

 

 

 

4. 테스트케이스

 

6 12
5 6 4 
4 3 3 
6 5 8 
5 1 4 
1 6 3 
6 2 6 
1 2 4 
3 2 8 
4 2 5 
5 3 5 
1 4 2 
2 4 8

답:

5
2 1
3 4
4 1
5 1
6 1

 

8 14
2 4 1 
7 6 7 
1 5 7 
1 4 6 
5 3 9 
4 1 5 
7 8 3 
6 1 4 
4 2 3 
5 6 3 
7 5 9 
7 1 9 
2 1 1 
7 4 6

답:7
2 1
3 5
4 2
5 1
6 1
7 4
8 7

 

24 45
20 16 5 
24 7 9 
24 18 6 
4 2 7 
23 5 7 
8 19 5 
1 6 3 
9 8 7 
2 3 5 
11 12 4 
4 20 1 
2 16 5 
22 11 1 
17 10 4 
3 7 4 
18 10 9 
21 2 5 
20 18 3 
5 10 5 
15 2 4 
14 10 7 
4 15 9 
20 10 8 
14 12 8 
12 8 1 
23 14 8 
15 24 9 
12 5 1 
15 8 3 
21 15 7 
12 7 6 
18 12 5 
13 7 2 
7 10 3 
24 5 1 
15 10 7 
3 2 2 
22 5 6 
3 16 4 
1 12 1 
9 17 3 
17 12 7 
8 12 8 
11 15 7 
4 9 5

답: (긁어서 구글 시트에 비교하면 쉽습니다)

23
2 15
3 7
4 20
5 12
6 1
7 12
8 12
9 8
10 5
11 12
12 1
13 7
14 12
15 8
16 2
17 12
18 12
19 8
20 18
21 15
22 11
23 5
24 5