问题 3546 --道路规划

3546: 道路规划

时间限制: 1 Sec  内存限制: 128 MB
提交: 3  解决: 3
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][216kb]

题目描述

N个村庄,编号从1N,请你建立一些道路,使得任意两个村庄可以相连。我们说两个村AB是相连的,当且仅当有一条公路在AB之间,或存在一个村庄C,有一条的道路连接着A和C之间,一条连接着B和C。

我们知道,已经有一些道路在一些村庄之间,你的工作是再建一些道路,使得所有的村庄连接并且所有的道路建造总和最低。

输入

第一行是一个整数N(3 <= N <= 100),表示村庄的数量。接下来N,每行包含N个整数,在这N行中的第i行的第j个整数Aij表示村庄i到村庄j建立道路的费用 (1 <= Aij <= 1000)

然后有一个整数Q(0 <= Q <= N *(N + 1)/2)。接下来再Q行,每一行包含两个整数ab(1 <= < b <= N),即村庄a和b之间已经建成道路。

输出

你应该输出一行包含一个整数,表示所有村庄都连接所要建设道路的最小费用。

样例输入

3
0 990 692
990 0 179
692 179 0
1
1 2

样例输出

179

提示


题目来源:pku 2421

来源

[提交][状态]