记录编号 131199 评测结果 AAAAAAAAAA
题目名称 [USACO Open09] 捉迷藏 最终得分 100
用户昵称 Gravatar乌龙猹 是否通过 通过
代码语言 C++ 运行时间 0.040 s
提交时间 2014-10-24 06:27:24 内存使用 1.22 MiB
显示代码纯文本
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

struct dx{
	int to,next;
};
dx jb[100001];
int sum;
int last[20001];

int n,m;
int jl,Ans,maxx;

int dis[20001];

void spfa(int);
void insert(int,int);

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 x,y;
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
	spfa(1);
	for(int i=1;i<=n;i++)
	{
		if(dis[i]>maxx)
		{
			maxx=dis[i];
			jl=i;
		}
	}
	printf("%d %d ",jl,maxx);
	for(int i=1;i<=n;i++)
	{
		if(dis[i]==maxx) Ans++;
	}
	printf("%d",Ans);
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}
void insert(int From,int To)
{
	sum++;
	jb[sum].to=To;
	jb[sum].next=last[From];
	last[From]=sum;
}
void spfa(int x)
{
	queue<int> q;
	bool flag[20001]={0};
	q.push(x);
	flag[x]=1;
	memset(dis,0x7f,sizeof(dis));
	dis[x]=0;
	while(!q.empty())
	{
		int k=q.front();
		int i=last[k];
		while(i)
		{
			int t=jb[i].to;
			if(dis[t]>dis[k]+1)
			{
				dis[t]=dis[k]+1;
				if(!flag[t])
				{
					q.push(t);
					flag[t]=1;
				}
			}
			i=jb[i].next;
		}
		flag[k]=0;
		q.pop();
	}
}