记录编号	390792	评测结果	AAAAAAAAAA
题目名称	Geodetic 集合	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-04-04 09:00:29	内存使用	0.32 MiB

#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set>
#define mylove Turkey;
using namespace std;
const int maxn=45;
const int inf=99999;
int n,m,x,y,a[maxn][maxn],v,u,h;
typedef int itn;
int floyd()
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int k=1;k<=n;k++)
	if(a[j][k]>a[j][i]+a[i][k])a[j][k]=a[j][i]+a[i][k];
}
typedef long long ll;
int main()
{	freopen("geo.in","r",stdin);
	freopen("geo.out","w",stdout);
 scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    a[i][j]=inf;
    for(int i=1;i<=m;i++)
    {
    	scanf("%d%d",&x,&y);
    	a[x][y]=1;
    	a[y][x]=1;
	}
	floyd();
	scanf("%d",&h);
	for(int i=1;i<=n;i++)
	a[i][i]=0;
	for(int i=1;i<=h;i++)
	{
		scanf("%d%d",&v,&u);
	//	cout<<min(u,v);
		for(int i=1;i<=n;i++)
		if(a[v][i]+a[i][u]==a[v][u])cout<<i;
	//	cout<<max(u,v);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}