取水

题目描述:

 Famer John希望把水源引入他的  \( N ( 1 \le N \le 300 ) \) 个牧场，牧场的编号是   \( 1 \dots N  \) 。他将水源引入某个牧场的方法有两个，一个是在牧场中打一口井，另一个是将这个牧场与另一个已经有水源的牧场用一根管道相连。在牧场  \( i \) 中打井的费用是  \( W_i  ( 1 \le W_i \le 10^5  ) \) 。把牧场  \( i \) 和  \( j \) 用一根管道相连的费用是  \( p_{ij}  ( 1 \le p_{ij} \le 10^5 ) , p_{ij} = p_{ji}, p_{ii} = 0 \) 。请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源。

输入格式:

 第1行: 一个正整数  \( N \) 。
第2～N+1行: 第  \( i+1 \) 行包含一个正整数  \( w_i \) 。
第N+2～2N+1行: 第N+1+i行包含  \( N \) 个用空格分隔的正整数, 第  \( j \) 个数表示  \( p_{ij} \) 。 

输出格式:

 最少要花多少钱才能够让他的所有牧场都有水源。

样例输入:

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

样例输出:

9

提示:

 【样例解释】

总共有四个牧场.在1号牧场打一口井需要5的费用,在2或者3号牧场打井需要4的费用,在4号牧场打井需要3的费用.在不同的牧场间建立管道需要2,3或4的费用. 

Farmer John需要在4号牧场打一口井,然后把所有牧场都用管道连到1号牧场上,总共的花费是3+2+2+2=9.

 

【数据范围】

对于30%的数据N<=10
对于70%的数据N<=100
对于100%的数据N<=300

时间限制: 1000ms
空间限制: 128MB

---