Problem
题目概述
给你一个无向图，边权都为 \(1\) ，求：离 \(1\) 号点最远的点的编号、最远的距离、有几个点是离 \(1\) 号点最远的。
思路
直接用：优先队列 \(BFS\)，先求出 \(1\) 号点到每个点的最短路，存到 \(dis\) 数组中，然后再求 \(max(dis[i])\) ，就搞定了。
错误原因
- 审题 & 做法错误。
- 不要想得太过于复杂，比如将最短路转换为负数等等...
- 细心
- 注意开 \(Long Long\)，因为答案有可能爆 \(int\) 。
代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 2e4 + 10, M = 5e4 + 10;
priority_queue<PII, vector<PII>, greater<PII> > q;
struct node {
int to, next;
} a[M * 2];
bool f[N];
int pre[N], k;
LL d[N];
int n, m, x, y;
void add(int x, int y) {
a[++k] = (node) {y, pre[x]};
pre[x] = k;
}
void bfs() {
memset(d, 0x3f, sizeof(d));
q.push(make_pair(0, 1));
d[1] = 0;
while (!q.empty()) {
PII h = q.top();
int p = h.second;
q.pop();
if (f[p]) continue;
f[p] = true;
for (int i = pre[p]; i; i = a[i].next) {
int to = a[i].to;
if (d[p] + 1 < d[to]) {
d[to] = d[p] + 1;
q.push(make_pair(d[to], to));
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
bfs();
LL ma = 0, cnt = 0;
for (int i = 1; i <= n; i++) ma = max(ma, d[i]);
for (int i = 1; i <= n; i++) if (d[i] == ma) cnt++;
for (int i = 1; i <= n; i++) {
if (d[i] == ma) {
printf("%d ", i);
break;
}
}
printf("%lld %lld", ma, cnt);
return 0;
}