페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5187

워터링 홀(Watering Hole) 1s 128MB

문제

농부 존은 N개의 목초지에 물을 공급하기로 결정했다 (1 ≤ N ≤ 300).

목초지는 각각 1부터 N으로 번호가 매겨져 있다.

목초지에 물을 공급하기 위해서는 우물을 건설하거나 이미 물이 있는 다른 목초지와 파이프를 통해 연결해야 한다.

 

목초지 i에서 우물을 파는데 드는 비용 W_i (1 ≤ W_i ≤ 100,000)와 

목초지 i와 j를 파이프로 연결하는 비용 P_{i,j} (1 ≤ P_{i,j} ≤100,000; \ P_{i,j} = P_{j,i};\ P_{i,i}=0)가 주어질 때,

 

농부 존이 그의 모든 목초지에 물을 공급하기 위해 지불해야 하는 최소 금액을 출력하는 프로그램을 작성하시오.


입력

첫 줄에는 목초지의 수 N(1 ≤ N ≤ 300)이 주어진다.

다음 N개의 줄에는 i번째 목초지에 우물을 파는데 드는 비용 W_i(1 ≤ W_i ≤ 100,000)가 순서대로 들어온다.

다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 목초지와 j번째 목초지를 연결하는데 드는 비용 P_{i,\ j}(1 ≤ P_{i,\ j} ≤ 100,000;\ \ P_{i,\ j} = P_{j,\ i}; \ P_{i,\ i} = 0)를 의미한다.


예제 

4

5

4

4

3

0 2 2 2

2 0 3 3

2 3 0 4

2 3 4 0
9


출처

USACO 2008 October Gold
로그인해야 코드를 작성할 수 있어요.