Agri-Net
면접 대비시간 제한1초메모리 제한1024 MB
N개 농장의 거리 행렬이 주어졌을 때, 모든 농장을 잇는 최소 길이의 광섬유 연결 합을 구합니다.
문제
농부 존(Farmer John)이 마을의 시장으로 당선되었다. 선거 공약 중 하나는 지역의 모든 농장에 인터넷을 연결하는 것이었다. 물론 그 일에는 당신의 도움이 필요하다. 존은 자신의 농장에 고속 회선을 신청했고, 이 연결을 다른 농부들과 나눌 계획이다. 비용을 줄이기 위해 그는 자신의 농장을 다른 모든 농장과 잇는 데 필요한 광케이블을 최소한으로 깔고자 한다. 농장 쌍마다 연결하는 데 드는 광케이블 길이가 주어진다. 모든 농장을 한데 잇는 데 필요한 광케이블의 최소 길이를 구해야 한다. 모든 농장은 다른 어떤 농장과 연결되어야 하며, 어느 농장에서 다른 어느 농장으로든 경로가 존재해야 한다.
입력
첫 줄에 농장의 수 N이 주어진다 (3 ≤ N ≤ 100). 이어지는 N개의 줄 각각에는 농장 i와 농장 1, 2, 3, ..., N 사이의 거리를 나타내는 음이 아닌 정수 N개가 주어진다. 각 정수는 32000보다 작다. 대각선 원소는 0이다. 농장 i와 자기 자신 사이의 거리는 이 문제에서 의미가 없기 때문이다.
출력
모든 농장을 연결하는 데 필요한 광케이블 길이 합의 최솟값을 나타내는 정수 하나를 출력한다.