AI题库 · GESP-C++七级题库
题目分享 #19781
城市规划
题目描述
A 国有n座城市,城市之间由m条双向道路连接,任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2....,n编号。第i(1≤i≤m)条双向道路连接城市ui与城市vi。
对于城市u和城市v而言,它们之间的连通度d(u,v)定义为从城市u出发到达城市 所需经过的双向道路的最少条数。由于道路是双向的,可以知道连通度满足d(u,v)=d(v,u),特殊地有d(u,u)=0。
现在 A 国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市,如果有多个满足条件的城市,则选取其中编号最小的城市。形式化地,你需要求出使得max1≤i≤nd(u,i)最小的u,若存在多个可能的u则选取其中最小的。
输入格式
第一行,两个正整数n,m,表示 A 国的城市数量与双向道路数量。
接下来m行,每行两个整数ui,vi,表示一条连接城市ui与城市vi的双向道路。
输出格式
输出一行,一个整数,表示建设难度最小的城市编号。如果有多个满足条件的城市,则选取其中编号最小的城市。
输入样例 1
3 3
1 2
1 3
2 3输出样例 1
1输入样例 2
4 4
1 2
2 3
3 4
2 4输出样例 2
2数据范围
对于40的测试点,保证1≤n≤300 。
对于所有测试点,保证1≤n≤2000,1≤m≤2000,1≤ui,vi≤n。
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。