문제 - 15591

문제접근

처음에는 모든 경로의 USADO를 구한다음에 질문에 답을 할려고했지만 N이 최대 5000여서 5000*5000*5000개인 경우에는 시간초과가 나오기 때문에 시도하지 않았다.
그래서 시키는 대로 BFS를 이용하여 첫 노드에서부터 연결된 노드로 이동시 K보다 크거나 같은 경우에만 Queue에 넣어주면서 결과값을 출력했다.
연결된 정점과의 USADO가 k보다 낮으면 그 이후의 정점은 확인 불필요하기 때문에 K보다 낮은 경우에는 queue에 넣어주지 않았다.

소스코드

import java.util.*;
import java.io.*;
public class Main {
    static ArrayList<Node> []graph;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();

        graph = new ArrayList[N+1];

        for(int i=1;i<=N;i++)
        {
            graph[i] = new ArrayList<Node>();
        }
        //간선 추가
        for(int i=0;i<N-1;i++)
        {
            int p = sc.nextInt();
            int q = sc.nextInt();
            int r = sc.nextInt();

            graph[p].add(new Node(q,r));
            graph[q].add(new Node(p,r));
        }

        //질문 처리
        for(int i=0;i<Q;i++)
        {
            int k = sc.nextInt();
            int v = sc.nextInt();
            int count = bfs(k,v,N);
            System.out.println(count);
        }
    }

    private static int bfs(int k, int v, int n) {
        int count =0;
        Queue<Node> q = new LinkedList<>();
        boolean visit[] = new boolean[n+1];
        q.offer(new Node(v,Integer.MAX_VALUE));
        visit[v] = true;

        while(!q.isEmpty())
        {
            Node cnt = q.poll();

            //연결된 간선
            for(Node next : graph[cnt.num])
            {
                //연결된 정점과의 USADO가 k보다 낮으면 그 이후의 정점은 확인 불필요
                if(visit[next.num]) continue;

                int minCost = Math.min(next.usado , cnt.usado);

                if(minCost >= k)
                {
                    q.offer(new Node(next.num,minCost));
                    count++;
                    visit[next.num] = true;
                }

            }
        }


        return count;
    }

    static class Node{
        int num;
        int usado;

        public Node(int num,int usado){
            this.num =num;
            this.usado = usado;
        }
    }
}