20分求助
查看原帖
20分求助
219935
JeffWang2019楼主2020/8/30 00:09
#include <bits/stdc++.h>
using namespace std;
const int inf=0x7fffffff;
struct no
{
    int to,w,next;
}e[200005];
priority_queue<pair<int,int> >q;
int dist[100005],head[100005];
int n,d,cnt=0,ans=0;
bool vis[100005];
void add(int u,int v,int w)
{
    e[++cnt]=(no){v,w,head[u]};
    head[u]=cnt;
}
void dij(int s)
{
    for(int i=1;i<=n;i++)
    {
        if(i==s)
        {
            dist[i]=0;
        }
        else
        {
            dist[i]=inf;
        }
    }
    q.push(make_pair(-dist[s],s));
    while(!q.empty())
    {
        int dis=q.top().first,x=q.top().second;
        q.pop();
        if(vis[x]) 
        {
            continue;
        }
        vis[x]=true;
        if(dis>dist[x]) 
        {
            continue;
        }
        for(int i=head[x]; i; i=e[i].next)
        {
            int y=e[i].to,w=e[i].w;
            if(!vis[y]&&dist[y]>dist[x]+w)
            {
                dist[y]=dist[x]+w;
                q.push(make_pair(-dist[y],y));
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&d); 
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v,1);
        add(v,u,1);
    }
    dij(1);
    for(int i=1;i<=n;i++)
    {
        if(dist[i]<d)
        {
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}
2020/8/30 00:09
加载中...