HDU 4707 Pet && 2013 ACM/ICPC Asia Regional Online —— Warmup

구 야 의 블 로그, 전재 출처 를 밝 혀 주세요.http://blog.csdn.net/acmmmm/article/details/11391877
제목: n 개의 점 과 거 리 를 정 합 니 다 dis
아래 는 나무 다.
0 시 거리 구하 기 > dis 점 은 몇 개 있 습 니까?
spfa 물 건 너
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <stdlib.h>
#include <cstdlib>
#include <math.h>
#include <set>
#include <vector>
#define inf 107374182
#define N 100001
#define im -1000000
#define ll int
using namespace std;
inline ll Max(ll a,ll b){return a>b?a:b;}
inline ll Min(ll a,ll b){return a<b?a:b;}
int d[N];
bool inq[N];
int n,m;
vector<int>G[N];
void spfa(){
    memset(inq,0,sizeof(inq));
    int i,u,v,len;
    for(i=0;i<n;i++)d[i]=inf;
    d[0]=0;
    queue<int>q; while(!q.empty())q.pop();
    q.push(0); inq[0]=true;
    while(!q.empty()){
        u=q.front() ; q.pop();
        len=G[u].size();
        for(i=0;i<len;i++){
            v=G[u][i];
            if(!inq[v]){
                d[v]=d[u]+1;
                inq[v]=true;
                q.push(v);
            }
        }
    }
}
int main()
{
    int T,i,u,v,DIS;scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&DIS);
        for(i=0;i<n;i++)G[i].clear();
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        spfa();
        int ans=0;
        for(i=0;i<n;i++)if(d[i]>DIS)ans++;
        printf("%d
",ans); } return 0; } /* 1 10 2 0 1 0 2 0 3 1 4 1 5 2 6 3 7 4 8 6 9 */

좋은 웹페이지 즐겨찾기