页面无法加载？点击这里可能会修复。
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

需要登录才能编写代码。