描述 Description
贝茜在和约翰玩一个 “捉迷藏” 的游戏．
她正要找出所有适合她躲藏的安全牛棚．一共有 N(2≤N≤20000)个牛棚，被编为 1 到 N 号．她知道约翰（捉牛者）从牛棚 1 出发．所有的牛棚由 M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚 1 距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安全牛棚．
输入格式 InputFormat
第 1 行输入两个整数 N 和 M，之后 M 行每行输入两个整数，表示一条路的两个端点．
输出格式 OutputFormat
仅一行，输出三个整数。第 1 个表示安全牛棚（如果有多个，输出编号最小的）；第 2 个表示牛棚 1 和安全牛棚的距离；第 3 个表示有多少个安全的牛棚。
样例输入 SampleInput
8 12
1 8
7 8
4 3
2 8
5 1
3 1
7 3
6 5
8 5
6 4
2 6
5 2
样例输出 SampleOutput
2 2 4
来源 Source
Silver
代码 Code
SPFA.
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
const int inf=0x7fffffff/27.11;
struct edge
{
int to,next,val;
}e[100005];
int head[20005],dis[20005];
bool used[20005];
deque <int> q;
int ans,tot,cnt;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
inline void spfa(int s)
{
int i,j,t,u,v,w;
while (!q.empty()) q.pop_front();
memset(used,false,sizeof(used));
for (i=1;i<=n;i++) dis[i]=inf;
q.push_back(s);dis[s]=0;used[s]=true;
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;w=e[i].val;
if (dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
if (!used[v])
{
used[v]=true;
if (!q.empty() && dis[q.front()]>dis[v]) q.push_front(v);
else q.push_back(v);
}
}
}
}
}
int main()
{
cnt=0;
read(n);read(m);
for (i=1;i<=m;i++) read(x),read(y),ins(x,y,1),ins(y,x,1);
spfa(1);
ans=tot=1;
for (i=2;i<=n;i++)
{
if (dis[i]>dis[ans])
{
ans=i;
tot=1;
}
else if (dis[i]==dis[ans]) tot++;
}
printf("%d %d %d\n",ans,dis[ans],tot);
return 0;
}