Hide and Seek 捉迷藏 USACO 最短路板子题

题目：

描述

贝茜在和约翰玩一个“捉迷藏”的游戏．她正要找出所有适合她躲藏的安全牛棚．一共有N(2≤N≤20000)个牛棚，被编为1到N号．她知道约翰（捉牛者）从牛棚1出发．所有的牛棚由M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚1距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安全牛棚．

输入

第1行输入两个整数N和M，之后M行每行输入两个整数，表示一条路的两个端点．

输出

仅一行，输出三个整数．第1个表示安全牛棚（如果有多个，输出编号最小的）；第2个表示牛棚1和安全牛棚的距离；第3个表示有多少个安全的牛棚．

样例

输入

6 7

3 6

4 3

3 2

1 3

1 2

2 4

5 2

输出

4 2 3

这道题是一道最短路板子题，我们直接上SPFA大法A掉他。

那我们现在就来复习一下SPFA吧。

SPFA类似于BFS，比bellman快，比Dijkstra慢不了多少，但是可以判断负环，我们这里就来写一下它基本模板。

如此图

我们首先访问到1，将它的dist赋为0,1连接到了2和4，因为他们初始赋的极大值，所以可以更新它们的最短路，也就是1,再由此松弛3和5，即可得到最远的路径。

代码如下：

#include <bits/stdc++.h>
using namespace std;

int ans1,ans2,ans3,n,m,dst[500010],nxt[500010],tot,vis[500010],en[500010],head[500010];

void add(int a,int b){
	tot++;
	en[tot]=b;
	nxt[tot]=head[a];
	head[a]=tot;
}//链式前向星，不会用邻接表也没有问题 

void spfa(){
	memset(dst,0x3f3f,sizeof(dst));
	queue<int>q;
	q.push(1);
	vis[1]=1;
	dst[1]=0;//给第一个点初始化 
	while(!q.empty()){
		int now=q.front();//取出队首元素 
		q.pop();//弹出 
		vis[now]=1;//标记此点 
		for(int i=head[now];i;i=nxt[i]){
			int v=en[i];//取出连接的点 
			if(dst[now]+1<dst[v]){//如果新松弛的路径长度小于当前的，则更新 
				dst[v]=dst[now]+1;
			}
			if(!vis[v]){
				vis[v]=1;
				q.push(v);//判断是否入过队列，没有则将它放进队，后面就可以对他进行操作 
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	spfa();
	
	for(int i=1;i<=n;i++){
		if(ans1<dst[i]){
			ans1=dst[i];
			ans2=i;
		}//求出最近的最远点的大小及位置 
	}
	cout<<ans2<<" "<<ans1<<" ";
	for(int i=1;i<=n;i++){
		if(dst[i]==ans1){
			ans3++;//统计最远点的个数 
		}
	}
	cout<<ans3;
	
	return 0;
}