#P13082. [NOISG 2017] Hotspot / 热门地点

    ID: 12713 Type: RemoteJudge 2500ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2017Special JudgeNOISG(新加坡)

[NOISG 2017] Hotspot / 热门地点

题目背景

译自 NOISG 2017 C.Hotspot

题目描述

一个国家有 nn 个城镇,这些城镇由 mm 条长度相同的道路连接。

这个国家有 kk 个公民。有趣的是,第 ii 位公民的家和办公室位于两个不同的城镇 AiA_iBiB_i。因此,第 ii 个公民每天都会在 AiA_iBiB_i 两个固定的城镇间往返。

为了节省时间,第 ii 个公民将选择长度最短的路径。如果 AiA_iBiB_i 间有多条最短路径,他 / 她将随机选择一条最短路径。第 ii 个公民通过城镇 ww 的期望为:

Ei(w)=Sw(Ai,Bi)S(Ai,Bi)E_i(w)=\dfrac{S_w(A_i,B_i)}{S(A_i,B_i)}

其中 S(u,v)S(u,v) 表示 uuvv 间的最短路数量,Sw(u,v)S_w(u,v) 表示 uuvv 间经过 ww 的的最短路数量。

小 D 是这个国家的总统。他想了解公民的需求,于是想在国家的某一个城镇上设立一个会议办公室,因为这样他就可以会见尽可能多的公民。确切地说,他想将会议办公室设立在使 i=0k1Ei(w)\sum\limits_{i=0}^{k-1}E_i(w) 最大的城镇 ww

你的任务是帮助小 D 找到符合要求的 ww。当有多个符合要求的城镇 ww 时,你可以输出其中的任何一个。

注意本题需要使用双精度浮点数

输入格式

第一行两个正整数 n,mn,m,分别表示城镇和道路的数量。

接下来 mm 行,每行两个整数 u,vu,v,表示城镇 uu 和城镇 vv 间有一条道路相连。

接下来一行包含一个正整数 kk,表示公民的个数。

接下来 kk 行,第 ii 行两个整数 Ai,BiA_i,B_i,表示第 ii 个公民的家和办公室的位置。

输出格式

一行一个整数表示使 i=0k1Ei(w)\sum\limits_{i=0}^{k-1}E_i(w) 最大的城镇 ww。如果有多个符合要求的解,输出其中的任何一个即可。

5 5
0 1
1 2
2 3
3 4
4 0
2
1 3
2 4
2
5 4
0 1
1 2
2 3
3 4
3
0 2
1 3
2 4
2
6 5
0 2
1 2
2 3
3 4
3 5
2
0 5
1 4
2
15 19
0 3
1 3
1 4
1 5
2 5
3 6
3 7
4 7
5 7
6 10
7 9
7 10
7 11
8 11
9 12
9 13
10 13
11 13
11 14
2
4 10
3 8
7

提示

样例解释

对于样例 1 和 3,显然选择城镇 33 也是正确的。

对于样例 4(如下图),在城镇 44 和城镇 1010 之间只有一条长度为 22 的最短路径,即 47104\to7\to10。此外,城镇 33 和城镇 88 之间只有一条长度为 33 的最短路径,即 371183\to7\to11\to8。 如果小 D 在城镇 77 建造会议办公室,那么 i=0k1Ei(w)=2\sum\limits_{i=0}^{k-1}E_i(w)=2 最大。

数据范围

请注意本题时限为 2.52.5 秒。

本题采用 Subtask\text{Subtask} 捆绑测试。

Subtask\text{Subtask} 分值 性质
11 44 图是一条链,且 n1000n\le1000m=n1m=n-1k=1k=1
22 55 图是一棵树,且 n1000n\le1000m=n1m=n-1k=1k=1
33 1111 图是一条链,且 n1000n\le1000m=n1m=n-1k200k\le200
44 1818 图是一棵树,且 n1000n\le1000m=n1m=n-1k200k\le200
55 2626 n1000n\le1000m8000m\le8000k20k\le20
66 3636 1n50001\le n\le50001m4×1041\le m\le 4\times 10^41k20001\le k \le2000

对于所有数据,保证 1n50001\le n\le50001m4×1041\le m\le 4\times 10^41k20001\le k \le20001u,v,Ai,Bin1\le u,v,A_i,B_i\le n,任何两个城镇之间的最短路不会超过 2152^{15} 条。