题意简叙：

奶牛贝西和农夫约翰（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; }

转载于:https://www.cnblogs.com/vercont/p/10210086.html

相关资源：JAVA上百实例源码以及开源项目