真的可以用Floyd诶......求完最短路，对于每个输入，从1到n依次判断每个顶点i是否满足dis[v][i]+dis[i][u]==dis[v][u]即可

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,a[51][51];
int main()
{
ios::sync_with_stdio(false);
freopen("geo.in","r",stdin);
freopen("geo.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
a[i][j]=0x3fffffff;
a[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int l,f;
cin>>l>>f;
a[l][f]=1;
a[f][l]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][k]+a[k][j]<a[i][j])
a[i][j]=a[i][k]+a[k][j];
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
int v,u;
cin>>v>>u;
for(int j=1;j<=n;j++)
if(a[v][j]+a[j][u]==a[v][u])
cout<<j<<" ";
cout<<endl;
}
while(1);
}

mark

floyd即可……因为……不判断“是否一定在某一条指定的最短路”，而是“只要在某一条最短路上”就过了……

题解说是什么 BFS + 递推：

本题考察图的有关知识。算法就是从每个点出发进行BFS扩展，按得到的BFS序列进行递推。
设 min[i, j]为从i到j的最短路长度
设f[i, j]表示从i到j点的最短路覆盖的节点集合，
f[i, j] = f[i, k] U {j} k={1..n} and (min[i, k]+1=min[i, j]）and (k,j)存在
对于输入的每个v,u对，输出f[v,u]中的所有点就可以了。

然后我用弗洛伊德写出来的时候顿时就泪目了

崇拝する