记录编号	38390	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 捉迷藏	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.146 s
提交时间	2012-04-18 12:03:53	内存使用	0.64 MiB

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <vector>
#define MAXN 20001
using namespace std;
int N,M;
vector<int> Map[MAXN];
int dist[MAXN],flag[MAXN];
const int INF=~0u>>3;
priority_queue<pair<int,int> > heap;
void Dijkstra()
{
    int u,v,nxt;
    for(int i=1;i<=N;i++) flag[i]=0,dist[i]=INF;
    dist[1]=0; heap.push(make_pair(0,1));
    while(!heap.empty())
    {
        u=heap.top().second;  heap.pop();
        if(flag[u]) continue;  flag[u]=1;
        for(unsigned int i=0;i<Map[u].size();i++)
        {
            v=Map[u][i]; nxt=dist[u]+1;
            if(!flag[v] && dist[v]>nxt)
            {
                dist[v]=nxt;
                heap.push(make_pair(-dist[v],v));
            }
        }
    }
    int id,ans=0,time;
    for(int i=1;i<=N;i++)
    {
        if(dist[i]<ans) continue;
        if(dist[i]>ans)
        {
            id=i;
            time=1;
            ans=dist[i];
            continue;
        }
        time++;
    }
    printf("%d %d %d\n",id,ans,time);
}
 
void init()
{
    scanf("%d %d\n",&N,&M); int x,y;
    for(int i=1;i<=M;i++)
    {
        scanf("%d %d\n",&x,&y);
        Map[x].push_back(y);
        Map[y].push_back(x);
    }
}
 
int main()
{
    freopen("hideseek.in","r",stdin);
    freopen("hideseek.out","w",stdout);
    init();
    Dijkstra();
    return 0;
}