记录编号	38380	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 捉迷藏	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.124 s
提交时间	2012-04-18 11:49:45	内存使用	0.42 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int oo=~0u>>2;

struct edge
{
	int t,cost;
	edge *next;
	edge(int _t,int _cost,edge *_next):t(_t),cost(_cost),next(_next){}
}*Map[20010];

int N,M,ans=-oo,tot,id,dist[20010];

void addedge(int s,int t,int cost)
{
	Map[s]=new edge(t,cost,Map[s]);
	Map[t]=new edge(s,cost,Map[t]);
}

int djs(int T)
{
	bool vis[20010];
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=N;i++)
		dist[i]=oo;
	dist[1]=0;
	priority_queue<pair<int,int> >heap;
	heap.push(make_pair(0,1));
	while(!heap.empty())
	{
		int u=heap.top().second;
		heap.pop();
		if(!vis[u])
		{
			vis[u]=true;
			for(edge *p=Map[u];p;p=p->next)
			{
				int t=p->t,cost=p->cost;
				if(!vis[t]&&dist[t]>dist[u]+cost)
				{
					dist[t]=dist[u]+cost;
					heap.push(make_pair(-dist[t],t));
				}
			}
		}
	}
}

int main()
{
	freopen("hideseek.in","r",stdin);
	freopen("hideseek.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		addedge(a,b,1);
	}
	djs(1);
	for(int i=2;i<=N;i++)
	{
		if(dist[i]>ans)
		{
			ans=dist[i];
			id=i;
			tot=1;
		}
		else if(dist[i]==ans)
			tot++;
	}
	printf("%d %d %d\n",id,ans,tot);
	return 0;
}