记录编号	155616	评测结果	AAAAAAAAAA
题目名称	Geodetic 集合	最终得分	100
用户昵称	OI88	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2015-03-29 17:58:45	内存使用	0.33 MiB

#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);
}