#P9578. 杨柳依依

    ID: 6194 传统题 2500ms 512MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1700普及+/提高-广度优先搜索最短路计数贡献法乘法原理

杨柳依依

题目描述

杨柳国的地图可以抽象成一张 nn 个点 mm 条边的无向连通图,每条边等长。图上有 kk 个人,其中第 ii 个人住在点 aia_i,每天都要去 bib_i 上班。他会选择一条长度最短的路径,如果有多条,则等概率随机一条。

小 G 想找一个点开便利店。具体来说,她定义了 Ei(w)E_i(w) 表示第 ii 个人经过点 ww 的概率,你需要帮助她找出 ∑i=0k−1Ei(w)\sum^{k-1}_{i=0} E_i(w) 最大的点 ww。如有多个,可输出任意一个。

题目描述

第一行,两个正整数 nn 和 mm。

接下来 mm 行,每行两个整数 uu 和 vv,表示一条边(节点编号从 00 到 n−1n − 1)。

接下来一行,一个正整数 kk。

接下来 kk 行,每行两个整数 aia_i 和 bib_i,表示第 ii 个人的起点和终点。

输出格式

一行,一个整数 ww 表示最佳便利店位置。

样例

样例 1

5 5
0 1
1 2
2 3
3 4
4 0
2
1 3
2 4
2 或 3

注意这里指的是 22 或 33 均可。

样例 2

5 4
0 1
1 2
2 3
3 4
3
0 2
1 3
2 4
2

样例 3

6 5
0 2
1 2
2 3
3 4
3 5
2
0 5
1 4
2 或 3

样例 4

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

fKbqSO.png

数据范围

  • 子任务 11,分值 44 分,保证图是一条链,n≤103n\le 10^3,m=n−1m=n-1,k=1k=1。
  • 子任务 22,分值 55 分,保证图是一条树,n≤103n\le 10^3,m=n−1m=n-1,k=1k=1。
  • 子任务 33,分值 1111 分,保证图是一条链,n≤103n\le 10^3,m=n−1m=n-1,k≤200k\le 200。
  • 子任务 44,分值 1818 分,保证图是一条树,n≤103n\le 10^3,m=n−1m=n-1,k≤200k\le 200。
  • 子任务 55,分值 2626 分,保证 n≤103n\le 10^3,m≤8×103m\le 8\times 10^3,k≤20k\le 20。
  • 子任务 66,分值 3636 分,保证 n≤5×103n\le 5\times 10^3,m≤4×104m\le 4\times 10^4,k≤2×103k\le 2\times 10^3。

对所有数据,保证任意两点间最短路径数量不超过 2152^{15},注意本题需使用 double。