记录编号	38376	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 捉迷藏	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.143 s
提交时间	2012-04-18 11:42:16	内存使用	0.57 MiB

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 20000 + 10, INF = ~0u>>2;
int n, m, a, b, s, t, k, d[N];
vector<int> G[N];
void Dijkstra() {
    priority_queue<pair<int, int> > q;
    bool l[N] = {0}; int u, v;
    for(int i=1; i<=n; i++) d[i] = INF;
    d[1] = 0; q.push(make_pair(0, 1));
    while(!q.empty()) {
        u = q.top().second; q.pop();
        if(!l[u]) {
            l[u] = 1;
            for(int i=0; i<G[u].size(); i++) {
                v = G[u][i];
                if(!l[v] && d[v] > d[u] + 1) {
                    d[v] = d[u] + 1;
                    q.push(make_pair(-d[v], v));
                }
            }
        }
    }
}
int main() {
    freopen("hideseek.in", "r", stdin);
    freopen("hideseek.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++) {
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    Dijkstra();
    s = *max_element(d+1, d+n+1);
    for(int i=1; i<=n; i++) if(d[i] == s) {
        k++;
        if(t == 0) t = i;
    }
    printf("%d %d %d\n", t, s, k);
    return 0;
}