논에 물 대기
면접 대비시간 제한2초메모리 제한128 MB
각 밭의 우물 파기 비용과 밭 사이 수로 연결 비용이 주어질 때, 가상의 수원 노드를 추가한 최소 신장 트리로 모든 밭에 물을 공급하는 최소 비용을 구합니다.
문제
농부는 자신이 운영하는 N개의 논 모두에 물을 공급하려고 한다. 물을 공급하는 방법은 두 가지이다. 어떤 논에는 직접 우물을 팔 수 있고, 이미 물이 공급되는 다른 논에서 물길을 연결해 물을 끌어올 수도 있다.
각 논에 우물을 파는 비용과 두 논 사이에 물길을 연결하는 비용이 주어진다. 모든 논에 물을 공급하는 데 필요한 최소 비용을 구하라.
입력
첫째 줄에 논의 수 N이 주어진다.
다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi가 순서대로 주어진다.
그다음 N개의 줄에는 각 줄마다 N개의 정수가 주어진다. i번째 줄의 j번째 수 Pi,j는 i번째 논과 j번째 논을 물길로 연결하는 비용이다.
조건은 다음과 같다.
- 1 ≤ N ≤ 300
- 1 ≤ Wi ≤ 100,000
- 1 ≤ Pi,j ≤ 100,000 (i ≠ j)
- Pi,j = Pj,i
- Pi,i = 0
출력
모든 논에 물을 공급하는 데 필요한 최소 비용을 출력한다.