题解 P5908 【猫猫和企鹅】
ShineEternal
2020-01-17 18:34:07
[link](https://blog.csdn.net/kkkksc03/article/details/104023513)
## solution:
发现其实就是求1号节点到其他节点最短距离小于等于d
单源最短路
dij求即可。
```cpp
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
vector<int>e[100005];
int dis[100005],vis[100005];
int main()
{
int n,d;
scanf("%d%d",&n,&d);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
dis[i]=2147483640;
}
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i];
if(dis[y]>dis[x]+1)
{
dis[y]=dis[x]+1;
q.push(make_pair(dis[y],y));
}
}
}
int ans=0;
for(int i=2;i<=n;i++)
{
if(dis[i]<=d)ans++;
}
printf("%d\n",ans);
return 0;
}
```