2070 - 道路规划

题目描述

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

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

输入

第一行是一个整数 N (3 \le N \le 100),表示村庄的数量。

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

然后有一个整数 Q (0 \le Q \le N \times (N + 1)/2)。

接下来再 Q 行,每一行包含两个整数 ab (1 \le a \lt b \le N),即村庄 ab 之间已经建成道路。

输出

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

样例

输入

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

输出

179
来源

并查集

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题