Informatica Online Judge

  통신망 긴급복구 [0962 / 03C2]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 162   Total Tried : 784


The Champion of this Problem (C++) : gs140742 - ms / 742byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

GSHS국의 통신망은 모두 n개의 기지국으로 구성된다.
어느 날 세계적인 해커 경곽이의 공격으로 모든 통신망이 끊어져서 통신이 불가능하게 되었다.

이에 지학이와 석환이는 통신망을 복구하기 위하여 각 노드들을 연결할 계획을 세웠다.
석환이와 지학이 k개의 통신망을 연결 완료 했을 때, 경곽이는 석환이와 지학이를 납치해버렸다.

이에 GSHS국의 최고의 프로그래머인 여러 분들이 남은 구간을 연결하여 통신망을 복구해야 한다.

단 통신망을 복구할 때, 드는 비용을 최소화 해야 하고 모든 기지국이 연결되어야 한다. 이를 작성하는 프로그램을 완성하시오.

Input

첫 번째 줄에 기지국의 수 n이 입력된다.
두 번째 줄부터 n줄에 걸쳐서 각 기지국을 연결하는데 드는 비용 w_ij(기지국 i와 기지국 j를 연결하는 비용)가 주어진다.
즉, 모든 기지국간을 연결하는 인접행렬 자료가 입력된다.
다음 줄에 이미 연결한 기지국의 개수 k가 주어진다.
다음 줄부터 k줄에 걸쳐서 연결된 기지국의 정보 a, b가 주어진다.

[입력값의 정의역]
1 <= n <= 1024
0 <= w_ij <= 10,000 ( 1 <= i, j <= n )
0 <= k <= n
1 <= a <= b <= n

Output

남은 기지국을 모두 연결하는데 드는 최소비용을 출력한다. (지학이와 석환이가 이미 연결해 둔 비용은 없는 제외 한다.)

IO Example

입력
4
0 1 1 2
1 0 2 3
1 2 0 4
2 3 4 0
2
1 2
3 4

출력
1

[해설]

처음에 1-2와 3-4가 연결되어 있으므로.

1 --(1)-- 2



3 --(4)-- 4

인 상태이다. 여기서 가장 적은 비용으로 모든 기지국을 연결하기 위해서는 (1-3), (1-4), (2-3), (2-4)중 (1-3)을 여결하는 것이 가장 저렴하다.


1 --(1)-- 2
|
(1)
|

3 --(4)-- 4


Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]