수도관 공사

Time Limit: 2000 msMemory Limit: 256 MBSilver III4Author: Super Admin최소 스패닝 트리가상 노드크루스칼

N개의 농장에 물을 공급해야 한다. 각 농장에 직접 우물을 파는 비용은 W_i이다. 또한 농장 i와 농장 j 사이에 수도관을 설치하는 비용은 P_{i,j}이다. 수도관이 연결된 농장들은 하나의 우물만으로 모두 물을 공급받을 수 있다.

모든 농장에 물을 공급하기 위한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 농장의 수 N이 주어진다. (1 <= N <= 300)

둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. i번째 정수는 농장 i에 우물을 파는 비용 W_i이다. (1 <= W_i <= 100,000)

셋째 줄부터 N개의 줄에 걸쳐 수도관 비용 행렬이 주어진다. j번째 줄의 i번째 정수는 P_{i,j}이다. (1 <= P_{i,j} <= 100,000)

출력

Problem Statistics

28

Total submissions

2

Accepted

7.1%

Acceptance rate

1

Unique solvers

모든 농장에 물을 공급하기 위한 최소 비용을 출력한다.

입력 1

출력 1

입력 2

출력 2