Bessie is playing hide and seek (a game in which a number of players hide and a single player (the seeker) attempts to find them after which various penalties and rewards are assessed; much fun usually ensues).
She is trying to figure out in which of N (2 <= N <= 20,000) barns conveniently numbered 1..N she should hide. She knows that FJ (the seeker) starts out in barn 1. All the barns are connected by M (1 <= M <= 50,000) bidirectional paths with endpoints A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i); it is possible to reach any barn from any other through the paths.
Bessie decides that it will be safest to hide in the barn that has the greatest distance from barn 1 (the distance between two barns is the smallest number of paths that one must traverse to get from one to the other). Help Bessie figure out the best barn in which to hide.
奶牛贝西和农夫约翰（FJ）玩捉迷藏，现在有N个谷仓，FJ开始在第一个谷仓，贝西为了不让FJ找到她，当然要藏在距离第一个谷仓最远的那个谷仓了。现在告诉你N个谷仓，和M个两两谷仓间的“无向边”。每两个仓谷间当然会有最短路径，现在要求距离第一个谷仓（FJ那里）最远的谷仓是哪个（所谓最远就是距离第一个谷仓最大的最短路径）？如有多个则输出编号最小的。以及求这最远距离是多少，和有几个这样的谷仓距离第一个谷仓那么远。
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains the endpoints for path i: A_i and B_i
第一行：两个整数N,M；
第2-M+1行：每行两个整数，表示端点A_i 和 B_i 间有一条无向边。
* Line 1: On a single line, print three space-separated integers: the index of the barn farthest from barn 1 (if there are multiple such barns, print the smallest such index), the smallest number of paths needed to reach this barn from barn 1, and the number of barns with this number of paths.
仅一行，三个整数，两两中间空格隔开。表示：距离第一个谷仓最远的谷仓编号（如有多个则输出编号最小的。），以及最远的距离，和有几个谷仓距离第一个谷仓那么远。
6 7 3 6 4 3 3 2 1 3 1 2 2 4 5 2
4 2 3
The farm layout is as follows:
Barns 4, 5, and 6 are all a distance of 2 from barn 1. We choose barn 4 because it has the smallest index.
这里谷仓4，5，6距离1号谷仓都是2，但是4编号最小所以输出4.因此最远距离是2且有3个谷仓，依次输出：2和3。
SPFA适用范围：
给定的图存在负权边（尽管这题没有负权边），这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。
算法思想：
我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int n,m,tot;
int head[20006],ver[500006],edge[500006],next[500006],d[20006];
queue<int> q;
bool v[20006];
int maxx=-2147483647,sum,where;
int read(){//快读
int a=0,b=1;
char ch=getchar();
while((ch<‘0‘||ch>‘9‘)&&(ch!=‘-‘)){
ch=getchar();
}
if(ch==‘-‘){
b=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘){
a=a*10+ch-‘0‘;
ch=getchar();
}
return a*b;
}
void add(int x,int y,int z){//建边
ver[++tot]=y;
edge[tot]=z;
next[tot]=head[x];
head[x]=tot;
}
void spfa(){
memset(d,0x3f,sizeof(d));// dist数组
memset(v,0,sizeof(v));// 是否在队列中
d[1]=0;
v[1]=1;
q.push(1);
while(q.size()){// 取出队头
int x=q.front();
q.pop();
v[x]=0;// 扫描所有出边
for(int i=head[x];i;i=next[i]){
int y=ver[i],z=edge[i];
if(d[y]>d[x]+z){// 更新，把新的二元组插入堆
d[y]=d[x]+z;
if(!v[y]){
q.push(y);
v[y]=1;
}
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){// 构建邻接表
int x,y;
x=read(),y=read();
// 无向图正反都需要建边
add(x,y,1);// 假定距离为1
add(y,x,1);// 假定距离为1
}
spfa();// 求单源最短路径
for(int i=1;i<=n;i++){
if(d[i]>maxx){// 查找最远距离
maxx=d[i];
where=i;// 记录最小的的一个位置
}
}
printf("%d %d ",where,maxx);// 输出位置和最大值
for(int i=1;i<=n;i++){// 统计与maxx距离相等的点的个数
if(d[i]==maxx){
sum++;
}
}
printf("%d",sum);// 输出个数
return 0;
}
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int n,m,tot;
int head[20006],ver[500006],edge[500006],next[500006],d[20006];
queue<int> q;
bool v[20006];
int maxx=-2147483647,sum,where;
int read(){
int a=0,b=1;
char ch=getchar();
while((ch<‘0‘||ch>‘9‘)&&(ch!=‘-‘)){
ch=getchar();
}
if(ch==‘-‘){
b=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘){
a=a*10+ch-‘0‘;
ch=getchar();
}
return a*b;
}
void add(int x,int y,int z){
ver[++tot]=y;
edge[tot]=z;
next[tot]=head[x];
head[x]=tot;
}
void spfa(){
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[1]=0;
v[1]=1;
q.push(1);
while(q.size()){
int x=q.front();
q.pop();
v[x]=0;
for(int i=head[x];i;i=next[i]){
int y=ver[i],z=edge[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
if(!v[y]){
q.push(y);
v[y]=1;
}
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int x,y;
x=read(),y=read();
add(x,y,1);
add(y,x,1);
}
spfa();
for(int i=1;i<=n;i++){
if(d[i]>maxx){
maxx=d[i];
where=i;
}
}
printf("%d %d ",where,maxx);
for(int i=1;i<=n;i++){
if(d[i]==maxx){
sum++;
}
}
printf("%d",sum);
return 0;
}
P2951 [USACO09OPEN]捉迷藏Hide and Seek
原文：https://www.cnblogs.com/xiongchongwen/p/11857605.html