Problem O: 修路

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $23$ 正确数量 $12$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 图论
有N个村庄,编号从1到N,你应该建一些道路,使得每两个村庄都可以相互连通。我们说两个村庄A和B是连通的,是指,
在A和B之间有一条路,或者存在一个村庄C,A与C之间有路,C与B之间有路。
即,如果村庄A和B是直接相连或者是通过其他的村庄相连,则A和B就是连通的。
我们知道在一些村庄之间已经存在道路,你的工作就是再修建一些道路,使得所有的村庄都能连接起来,并且所修的道
路的长度都是最小的。

本题多组输入,每组输入的第一行是一个整数N (3 <= N <= 100),即村庄的数目。然后是N行,其中的i‐th包含N个整数,而这些N个整数的j‐th

是距离(距离应该是一个整数,在[1,1000])之间的村庄i和村庄j。
然后是整数Q (0 <= Q <= N * (N + 1) / 2),然后是Q行,每一行包含两个整数a和b (1 <= a < b <= N),这意味
着a村和b村之间的道路已经建立。
对于每一组输入都应该输出一行包含一个整数,这是所有要构建的道路的长度,这样所有的村庄都是连接的,并且这个值是最小的。
3
0 990 692
990 0 179
692 179 0
1
1 2
179
本题多组输入