농부 존은 그의 \(N\) 개의 목초지에 물을 대기로 결정했습니다. 목초지는 편리하게 \(1\)부터 \(N\)까지 번호가 매겨져 있습니다.

그는 특정 목초지에 직접 우물을 파거나, 이미 물이 공급되고 있는 다른 목초지와 파이프를 통해 연결함으로써 목초지에 물을 가져올 수 있습니다.

목초지 \(i\)에 우물을 파는 비용은 \(W_i\) 입니다. 목초지 \(i\)와 \(j\)를 파이프로 연결하는 비용은 \(P_{i,j}\) 입니다. (\(P_{i,j} = P_{j,i}\) 이며, \(P_{i,i} = 0\) 입니다.)

모든 목초지에 물을 공급하기 위해 농부 존이 지불해야 하는 최소 비용을 구하세요.

입력

첫 번째 줄에 목초지의 개수 \(N\)이 주어진다.

\((1 \le N \le 300)\)

이후 \(N\)개의 줄에 걸쳐 우물을 파는 비용이 주어진다. \(i+1\)번째 줄에는 단일 정수 \(W_i\)가 주어진다.

\((1 \le W_i \le 100,000)\)

이후 \(N\)개의 줄에 걸쳐 파이프 연결 비용이 주어진다. \(N+1+i\)번째 줄에는 \(N\)개의 정수가 공백으로 구분되어 주어지며, 이 중 \(j\)번째 정수는 \(P_{i,j}\)를 의미한다.

\((1 \le P_{i,j} \le 100,000)\)

입력으로 주어지는 모든 값은 정수이다.

출력

모든 목초지에 물을 대는 데 필요한 최소 비용을 나타내는 단일 정수를 한 줄에 출력한다.

힌트

총 4개의 목초지가 있습니다. 우물을 파는 비용은 목초지 1은 5, 목초지 2와 3은 4, 목초지 4는 3입니다.

파이프 연결 비용은 연결하는 목초지에 따라 각각 2, 3, 4가 듭니다.

출력 상세 설명:

농부 존은 4번째 목초지에 우물을 파고(비용 3), 나머지 모든 목초지를 1번째 목초지와 연결(비용 2 + 2 + 2)할 수 있습니다.

이 경우 총비용은 \(3 + 2 + 2 + 2 = 9\)가 됩니다.

출처

USACO 2018 December Contest, Silver

Line 1: \(N\) (\(1 \le N \le 300\)). Next \(N\) lines: \(W_i\). Next \(N\) lines: the \(N \times N\) symmetric pipe-cost matrix \(P\).

Print the minimum total watering cost.

riseoj 작성

출처 Online Judge > GoldOJ