Farmer John 决定把水引到N个牧场 N (1 <= N <= 300),牧场正好从1..N编号。FJ可以用两种方法来引水:
(1)在牧场上挖一口水井;
(2)从其它已经有水的牧场连一根水管。
在牧场i挖水井的费用为W_i (1 <= W_i <= 100,000),在牧场i和j之间连水管的费用为P_ij (1 <= P_ij <=100,000; P_ij = P_ji; P_ii=0)
请算出FJ把水引到所有牧场的最小费用。
Farmer John 决定把水引到N个牧场 N (1 <= N <= 300),牧场正好从1..N编号。FJ可以用两种方法来引水:
(1)在牧场上挖一口水井;
(2)从其它已经有水的牧场连一根水管。
在牧场i挖水井的费用为W_i (1 <= W_i <= 100,000),在牧场i和j之间连水管的费用为P_ij (1 <= P_ij <=100,000; P_ij = P_ji; P_ii=0)
请算出FJ把水引到所有牧场的最小费用。
第1行: 1个整数 N
第2..N + 1行: 只有1个整数 W_i
第N+2..2N+1行:每有 N 个空格分开的整数,第j个表示 P_ij
第1行: 1个整数表示引水到所有牧场的最小费用。
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
9
样例说明: 一共有4个牧场。挖水井的代价分别为5,4,4,3. 在不同牧场之间连水管的代价分别是 2, 3, 和 4 。Farmer John 在第4个牧场挖一口井,然后分别从第4个牧场连到其它牧场,代价为: 3 + 2 + 2 + 2 = 9.