#G. 【入门】道路规划

    Type: Default 1000ms 128MiB

【入门】道路规划

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

有N个村庄,编号从1到N,请你建立一些道路,使得任意两个村庄可以相连。我们说两个村A和B是相连的,当且仅当有一条公路在A与B之间,或存在一个村庄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行,每一行包含两个整数a和b(1 <= a < b <= N),即村庄a和b之间已经建成道路。

输出格式

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

样例

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

提示


第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45