Description
贝茜在和约翰玩一个“捉迷藏”的游戏．
她正要找出所有适合她躲藏的安全牛棚．一共有N(2≤N≤20000)个牛棚，被编为1到N号．她知道约翰（捉牛者）从牛棚1出发．所有的牛棚由M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚1距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安全牛棚．
Input
第1行输入两个整数N和M，之后M行每行输入两个整数，表示一条路的两个端点．
Output
仅一行，输出三个整数．第1个表示安全牛棚（如果有多个，输出编号最小的）；第2个表示牛棚1和安全牛棚的距离；第3个表示有多少个安全的牛棚．
Sample Input
6 7 3 6 4 3 3 2 1 3 1 2 2 4 5 2
Sample Output
4 2 3
HINT
Source
SPFA 对于一个到达过的点，更新他的最小值，没到达的更新当前值，
记录到达每个点的次数，最后找出最长距离判断判断就好了。
1 #include2 #include 3 #include 4 5 inline void read(int &x) 6 { 7 x=0; register char ch=getchar(); 8 for(; ch>'9'||ch<'0'; ) ch=getchar(); 9 for(; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';10 }11 12 const int M(50005);13 const int N(20005);14 15 int n,m,head[N],sumedge;16 int _v[M<<1],_nex[M<<1];17 inline void ins(int u,int v)18 {19 _v[++sumedge]=v,_nex[sumedge]=head[u];head[u]=sumedge;20 _v[++sumedge]=u,_nex[sumedge]=head[v];head[v]=sumedge;21 }22 23 bool inq[N];24 int dis[N],cnt[N],id[M];25 26 inline void SPFA(int s)27 {28 for(int i=1; i<=n; ++i) dis[i]=-1;29 std:: queue que;30 dis[s]=0; que.push(s);31 for(int u,v; !que.empty(); )32 {33 u=que.front(); que.pop(); inq[u]=0;34 for(int i=head[u]; i; i=_nex[i])35 {36 if(dis[_v[i]]==-1)37 {38 cnt[_v[i]]++;39 dis[_v[i]]=dis[u]+1;40 if(!inq[_v[i]])41 {42 que.push(_v[i]);43 inq[_v[i]]=true;44 }45 }46 else if(dis[_v[i]]>dis[u]+1)47 {48 cnt[_v[i]]++;49 dis[_v[i]]=dis[u]+1;50 if(!inq[_v[i]])51 {52 que.push(_v[i]);53 inq[_v[i]]=true;54 }55 }56 }57 58 }59 }60 61 int Presist()62 {63 read(n),read(m);64 for(int u,v; m--; )65 read(u),read(v),ins(u,v);66 SPFA(1); int now=-1,pos,num;67 for(int i=1; i<=n; ++i)68 if(dis[i]>now) now=dis[i],pos=i,num=cnt[i];69 printf("%d %d ",pos,now); num=0;70 for(int i=1; i<=n; ++i) num+=(dis[i]==now);71 printf("%d\n",num);72 return 0;73 }74 75 int Aptal=Presist();76 int main(int argc,char**argv){;}