실버 III농부 존은 그의 \(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.
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
9