城市规划 题目描述 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。
正确答案：参考程序（Python）：n,m=map(int,input().split());g=[[]for _ in range(n+1)];for _ in range(m):u,v=map(int,input().split());g[u].append(v);g[v].append(u);from collections import deque;best_u=1;best_d=10**9;for s in range(1,n+1):dist=[-1]*(n+1);dist[s]=0;q=deque([s
试卷来源：202512 CCF-GESP编程能力等级认证C++七级真题