stdKonjac's Blog

An AC a day keeps the WA away ~

【Geodetic集合】

题目描述

图 G 是一个无向连通图,没有自环,并且两点之间至多只有一条边。我们定义顶点 v,u 最短路径就是从 v 到 u 经过边最少的路径。所有包含在 v-u 的最短路径上的顶点被称为 v-u 的 Geodetic 顶点,这些顶点的集合记作 I(v, u)。
我们称集合 I(v, u)为一个 Geodetic 集合。
例如下图中,I(2, 5)={2, 3, 4, 5},I(1, 5)={1, 3, 5},I(2, 4)={2, 4}。

《【Geodetic集合】》

给定一个图 G 和若干点对 v,u ,请你分别求出 I(v,u)。

输入格式

第一行两个整数 n 和 m,分别表示图G的顶点数和边数(顶点编号 1~n)
下接 m 行,每行两个整数 a,b 表示顶点 a 和 b 之间有一条无向边。
第 m+2 行有一个整数 k ,表示给定的点对数。
下接k行,每行两个整数 v,u。

输出格式

输出共 k 行,每行对应输入文件中每一个点对 v,u(v≠u),按顶点编号升序输出 I(v, u) 。同一行的每个数之间用空格分隔。

样例数据 1

输入

5 6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4

输出

2 3 4 5
1 3 5
2 4

备注

【数据范围】
100% 的数据,n≤40;m≤500;k≤800

根据N的范围,可以先Floyed求出两点之间最短路(逗比的我对每个点SPFA一遍也是醉)然后对于每个询问,枚举1~n 如果dis[i][k]+dis[k][j]=dis[i][j]那么k显然一定在i~j的最短路上,把所有k求出来存在栈中排个序即可。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.