Informatica Online Judge

  Agri-Net [0289 / 0121]

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


The Champion of this Problem (C++) : gs19022 - 0ms / 645byte
My Best Submission (C++) : N/A

[]

Background

농부 존은 마을 이장으로 선출되었다. 그의 공약중의 하나는 이 마을 전체에 인터넷 망을 설치하는 것이었다. 그래서 존은 당신에게 도움을 요청했다.

농부 존은 초고속 통신망을 그의 농장에 설치하길 원하고, 마을의 다른 농장과에도 인터넷이 가능하도록 연결하고자 한다. 가장 적은 비용을 위하여 모든 농장을 연결하는 광 케이블의 길이를 최소화 하고자한다.

두 농장간의 거리는 100,000을 넘지 않는다. 농부 존을 도와줄 프로그램을 작성하시오.

Input

첫 번째 줄에 농장의 수 N이 주어진다. N은 3이상 100이하의 자연수이다.
두 번째 줄부터 N*N의 인접행렬이 주어진다. 이 행렬은 각 농장을 연결하는 거리를 의미한다.

Output

모든 농장에 인터넷 망을 연결하기 위한 최소 광케이블의 길이를 출력한다.

IO Example

입력
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

출력
28

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