这是无权图单源最短路。先从 1 号点做 BFS，得到每个点的最短层数，再统计最远距离、最小编号和该距离出现次数。
OJ: luogu
题目 ID: P2951
难度:普及-
标签:最短路图论bfs
日期: 2026-06-20 03:45
题意
给一张无权无向图，农夫在 1 号谷仓。
要求找出：
- 距离
1号谷仓最远的谷仓编号（如果有多个，取编号最小） - 这个最远距离
- 距离等于这个最远距离的谷仓个数
思路
先看一个最直接的小数据暴力：
cpp
// brute.cpp：用 Floyd 求 1 号点到所有点的最短距离。
// 只适合小数据，但逻辑最直接。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int INF = 1e9;
int n, m;
int dist_arr[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
dist_arr[i][j] = 0;
}
else {
dist_arr[i][j] = INF;
}
}
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
dist_arr[u][v] = 1;
dist_arr[v][u] = 1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist_arr[i][k] + dist_arr[k][j] < dist_arr[i][j]) {
dist_arr[i][j] = dist_arr[i][k] + dist_arr[k][j];
}
}
}
}
int best_id = 1;
int best_dist = -1;
int count = 0;
for (int i = 1; i <= n; i++) {
if (dist_arr[1][i] > best_dist) {
best_dist = dist_arr[1][i];
best_id = i;
count = 1;
}
else if (dist_arr[1][i] == best_dist) {
count++;
}
}
cout << best_id << ' ' << best_dist << ' ' << count << '\n';
return 0;
}暴力做法是 Floyd：
- 先求任意两点最短路
- 只看
1号点到所有点的距离 - 找最大值，并统计最小编号和数量
这个思路很直观，但这题其实根本不需要全源最短路。
因为图是：
- 无权图
- 单源
1
这两个信号一出来，就应该直接想到 BFS。
从 1 号点开始做 BFS 时：
- 第 0 层是
1 - 第 1 层是离
1一条边的点 - 第 2 层是离
1两条边的点
因此，BFS 求出来的 dist[i] 就是：
1到i的最短路径边数
接下来只要顺序扫一遍：
- 如果发现更大的距离，就更新答案
- 如果发现相同的最大距离，就给数量加一
- 因为是按编号从小到大扫，所以第一次遇到这一最远距离的点，自然就是编号最小的答案
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000 + 5;
const int MAXM = 50000 * 2 + 5;
const int INF = 1e9;
int n, m;
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
int dist_arr[MAXN];
void init_graph() {
edge_cnt = 0;
for (int i = 1; i <= n; i++) {
head[i] = 0;
dist_arr[i] = INF;
}
}
void add_edge(int u, int v) {
edge_cnt++;
to[edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void bfs(int start) {
queue<int> q;
dist_arr[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
if (dist_arr[v] != INF) {
continue;
}
dist_arr[v] = dist_arr[u] + 1;
q.push(v);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
init_graph();
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
bfs(1);
int best_id = 1;
int best_dist = -1;
int count = 0;
for (int i = 1; i <= n; i++) {
if (dist_arr[i] > best_dist) {
best_dist = dist_arr[i];
best_id = i;
count = 1;
}
else if (dist_arr[i] == best_dist) {
count++;
}
}
cout << best_id << ' ' << best_dist << ' ' << count << '\n';
return 0;
}复杂度
一次 BFS：
最后扫描所有点：
总复杂度：
空间复杂度：
总结
这题最重要的是别被“最短路”三个字带偏。
它虽然属于最短路题，但本质上只是：
- 无权图
- 单源最短路
- 找最远层
这种题最稳的选择就是 BFS。
