题解 | Hide and Seek-牛客假日团队赛9K题

K-Hide and Seek_牛客假日团队赛9

https://ac.nowcoder.com/acm/contest/1071/K

题目描述

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 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 \leq M \leq 50,000)$ bidirectional paths with endpoints $A_i$ and $B_i (1 \leq A_i \leq N; 1 \leq B_i \leq 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.

输入描述:

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Line i+1 contains the endpoints for path i: Ai and Bi

输出描述:

* 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.

示例1

输入

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.

解答

题意简叙：
奶牛贝西和农夫约翰（FJ）玩捉迷藏，现在有N个谷仓，FJ开始在第一个谷仓，贝西为了不让FJ找到她，当然要藏在距离第一个谷仓最远的那个谷仓了。现在告诉你N个谷仓，和M个两两谷仓间的“无向边”。每两个仓谷间当然会有最短路径，现在要求距离第一个谷仓（FJ那里）最远的谷仓是哪个（所谓最远就是距离第一个谷仓最大的最短路径）？如有多个则输出编号最小的。以及求这最远距离是多少，和有几个这样的谷仓距离第一个谷仓那么远。

分析：
这道题其实就是裸单源最短路，还是dijkstra跑一遍1到其他所有点的，然后取编号最小，距离最长，个数最多输出就行。其他见代码：

代码：

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int > > > q;
vector<int>e[50005];
int dis[50005];
int vis[50005];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int tmp;
		tmp=y;
		e[x].push_back(tmp);
		tmp=x;
		e[y].push_back(tmp);
	}
	//从这里开始是模板
	for(int i=1;i<=n;i++)
	{
		dis[i]=2147483647;
	}
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		int x=q.top().second;
		q.pop();
		if(vis[x]==1)
		continue;
		vis[x]=1;
		for(int i=0;i<e[x].size();i++)
		{
			int y=e[x][i];
			if(dis[x]+1<dis[y])
			{
				dis[y]=dis[x]+1;
				q.push(make_pair(dis[y],y));
			}
		}
	}
	//到这里结束
	int number;
	int ans;
	int tmp=0;
	for(int i=1;i<=n;i++)
	{
		if(dis[i]>tmp)//一直找最大，找到了，就先有一个ans，编号保存，更新最长距离
		{
			tmp=dis[i];
			number=i;
			ans=1;
		}
		else
		if(dis[i]==tmp)//否则说明有好几个点，直接累加ans就行
		{
			ans++;
		}
	}
	printf("%d %d %d\n",number,tmp,ans);
	return 0;
}

来源：ShineEternal