1223. Load

单点时限: 2.0 sec

内存限制: 256 MB

近些时候华东师大闵行校区越发扩大,建筑越来越多,粗心的建筑商猛然发现

并不是所有建筑物都是相连的,换句话说,有些建筑还没有路可以到达。

现在你有手里有一份各个建筑之间铺设一条路的造价表,以及一份已经铺好的路

的清单,请你帮助建筑商铺设一些路使所有的建筑都可互相到达或间接到达。

输入格式

第一行一个整数 T,表示一下的 case 总数。而每个 case 格式如下 :

第一行有两个整数 n(n<=300), m(m<(n*(n+1)/2))

接下来是一个 n*n 的方阵表示建筑 i 到 j 的造价,我们保证

cost[i][j] = cost[j][i]; cost[i][i] = 0; cost[i][j] >= 0;

之后有 m 行,每行有二个整数 u, v, 表示 u 到 v 已经铺好路。

输出格式

每个 case 输出一行,只包含一个整数,为各个建筑可互相到达的最小造价

样例

Input
1
3 1
0 3 1
3 0 3
1 3 0
2 1
Output
1

20 人解决,32 人已尝试。

29 份提交通过,共有 89 份提交。

5.3 EMB 奖励。

创建: 13 年前.

修改: 2 年,9 月前.

最后提交: 1 年,7 月前.

来源: LSP

题目标签