문제
농부 존은 N개의 목초지에 물을 공급하기로 결정했다 (1 <= N <= 300).
목초지는 각각 1부터 N으로 번호가 매겨져 있다.
목초지에 물을 공급하기 위해서는 우물을 건설하거나 이미 물이 있는 다른 목초지와 파이프를 통해 연결해야 한다.
목초지 i에서 우물을 파는데 드는 비용 W_i (1 <= W_i <= 100,000)와
목초지 i와 j를 파이프로 연결하는 비용 P_ij (1 <= P_ij <=100,000; P_ij = P_ji; P_ii=0)가 주어질 때,
농부 존이 그의 모든 목초지에 물을 공급하기 위해 지불해야 하는 최소 금액을 출력하는 프로그램을 작성하시오.
입력
첫 줄에는 목초지의 수 N(1 ≤ N ≤ 300)이 주어진다.
다음 N개의 줄에는 i번째 목초지에 우물을 파는데 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다.
다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 목초지와 j번째 목초지를 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)를 의미한다.
예제1
입력
4
5
4
4
3
0222
2033
2304
2340
출력
9
출처
USACO 2008 October Gold