A22045. 城市规划
填空题
困难
知识点
题目描述
城市规划
题目描述
A 国有n座城市，城市之间由m条双向道路连接，任意一座城市均可经过若⼲条双向道路到达另一座城市。城市依次以1,2,...,n编号。第i （1≤i≤m）条双向道路连接城市ui与城市vi 。
对于城市u和城市v⽽言，它们之间的连通度d(u,v) 定义为从城市u出发到达城市v所需经过的双向道路的最少条数。由于道路是双向的，可以知道连通度满足d(u,v) =d(v,u) ，特殊地有d(u,v) =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 。
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2005;
int n, m;
vector<int> e[N];
int d[N], q[N];
void bfs(int u) {
for (int i = 1; i <= n; i++) d[i] = n + 1;
d[u] = 0;
q[1] = u;
int ql = 1, qr = 1;
while (ql <= qr) {
int x = q[ql++];
for (auto y : e[x]) {
if (d[x] + 1 < d[y]) {
d[y] = d[x] + 1;
q[++qr] = y;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
int ans = 1;
for (int i = 1; i <= n; i++) {
bfs(i);
if (d[i] < d[ans]) ans = i;
}
printf("%d\n", ans);
return 0;
}
上一题
下一题