행성 연결
면접 대비시간 제한1초메모리 제한256 MB
각 행성 쌍의 연결 비용이 주어질 때 모든 행성을 연결하는 최소 신장 트리의 비용 합을 구합니다.
문제
홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해 N개의 행성 사이에 플로우를 설치하려고 한다.
두 행성 사이에 플로우를 설치하면 제국의 함선과 무역선은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간에 이동할 수 있다. 하지만 치안을 유지하려면 플로우 안에 제국군을 주둔시켜야 한다.
모든 행성 사이에 플로우를 설치하고 그 안에 제국군을 주둔시키면 제국의 재정이 악화되므로, 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소로 줄이려 한다.
N개의 행성은 정수 1,…,N으로 나타내고, 행성 i와 행성 j 사이의 플로우 관리 비용은 Cij이며, i = j인 경우 이 값은 항상 0이다.
제국의 참모인 당신은 황제 윤석이를 도와 제국 안의 모든 행성을 연결하고 그 유지비용을 최소화하자. 이때 플로우의 설치비용은 무시한다.
입력
첫째 줄에 행성의 수 N (1 ≤ N ≤ 1000)이 주어진다.
둘째 줄부터 N+1번째 줄까지 각 행성 사이의 플로우 관리 비용이 N x N 행렬 (Cij), (1 ≤ i, j ≤ N, 1 ≤ Cij ≤ 100,000,000, Cij = Cji, Cii = 0)로 주어진다.
출력
모든 행성을 연결했을 때 최소 플로우 관리비용을 출력한다.