Time Limit: 1s
Memory Limit: 128MB
WithCS 농장 아저씨가 이장님으로 선출되었습니다! 공약중에 하나는 동네에 인터넷 망을 구축하여 모든 농장이 연결되도록 하는 것이었습니다. 물론, 이를 해결하기 위해 바로 당신의 도움이 필요합니다. WithCS 농장 아저씨는 농장과 농장을 인터넷으로 연결하기 위해 광랜으로 잇기로 하였습니다. 비용을 최소화 하기 위해 랜선의 길이가 최소화되기를 원하고 있습니다. 여러분들은 농장과 농장 사이에 필요한 랜선의 길이를 알게되며 이를 가지고 모든 농장을 연결하기 위한 최소 랜선 길이를 알아내야 합니다. 두 농장의 최대 거리는 100,000을 넘지 않습니다.
* Line 1 : 단일 정수, N
- N : 농장의 수
* Line 2 ~ N+1 : 농장간의 거리를 담은 정수 배열
- 각각의 라인은 N개의 정수를 가지고 있음
- 각각의 정수는 (라인번호 - 1)번째 농장과 (배열 내 정수번호)번째 농장간의 거리를 나타냄
모든 농장을 연결할 수 있는 최소 길이를 단일 정수로 출력함
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
28
데이터 패킷은 하나의 농장에서 다른 농장을 가기 위해 중간에 여러개의 농장을 거칠 수 있습니다. 이를 감안하여 모든 농장을 연결하세요.