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;
}