记录编号	38407	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 捉迷藏	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.135 s
提交时间	2012-04-18 16:21:28	内存使用	0.50 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
typedef vector<int>vec;
vec a[20010];
void spfa();
int n,m,ans1,ans2=0,ans3=0;
int main()
{
	freopen ("hideseek.in","r",stdin);
	freopen ("hideseek.out","w",stdout);
	cin>>n>>m;
	for (int i=0;i<m;i++)
	{
		int b,c;
		scanf("%d%d",&b,&c);
		a[c].push_back(b);		
		a[b].push_back(c);
	}
	spfa();
	cout<<ans1<<' '<<ans2<<' '<<ans3;
	return 0;
}

void spfa()
{
	int q[100001]={0};
	int w[20001]={0};
	int tou,wei;
	tou=wei=1;
	q[1]=1;
	for (int i=1;i<=n;i++)
		w[i]=10000000;
	w[1]=0;
	bool used[20001]={0};
	used[1]=1;
	while (tou<=wei)
	{
		for (int i=0;i<a[q[tou]].size();i++)
		{
			int j;
			j=a[q[tou]][i];
			if (!used[j]&&w[q[tou]]+1<w[j])
			{
				used[j]=1;
				w[j]=w[q[tou]]+1;
				wei++;
				q[wei]=j;
			}
		}
		if (w[q[tou]]>ans2||(w[q[tou]]==ans2&&q[tou]<ans1))
		{
			ans1=q[tou];
			ans2=w[q[tou]];
		}
		tou++;
	}
	for (int i=1;i<=n;i++)
	{
		if (w[i]==ans2)
			ans3++;
	}
}