70分,WA了三个点,代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 2e4 + 5;
int cnt = 0, hd[N], dis[N];
bool vis[N];
struct node
{
int d;
int pos;
bool operator < (const node &p) const
{
return d > p.d;
}
};
struct edge
{
int to;
int nxt;
} e[50005];
priority_queue<node> q;
void insert(int u, int v)
{
e[++cnt] = {v, hd[u]};
hd[u] = cnt;
}
void dijkstra(int s)
{
dis[s] = 0;
q.push({0, s});
while (!q.empty())
{
node head = q.top();
int x = head.pos;
q.pop();
if (vis[x])
{
continue;
}
vis[x] = true;
for (int i = hd[x]; i != 0; i = e[i].nxt)
{
int y = e[i].to;
if (dis[y] > dis[x] + 1)
{
dis[y] = dis[x] + 1;
if (!vis[y])
{
q.push({dis[y], y});
}
}
}
}
}
int main()
{
int n, m;
cin >> n >> m;
memset(dis, 999999, sizeof(dis));
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
insert(u, v);
insert(v, u);
}
dijkstra(1);
int ans = *max_element(dis + 1, dis + n + 1), tot = 0;
cout << max_element(dis + 1, dis + n + 1) - dis << " " << ans << " ";
for (int i = 1; i <= n; i++)
{
tot += (dis[i] == ans);
}
cout << tot;
return 0;
}