가장 가까운 대피소
플래티넘 I의견: 0
\(N\)개의 지점이 트리로 연결된 도시가 있다. 각 도로에는 양의 길이가 있다. 일부 지점에는 대피소가 설치되어 있다.
\(Q\)개의 질의가 주어진다. 각 질의는 지점 \(q\)가 주어지며, \(q\)에서 가장 가까운 대피소까지의 거리를 출력해야 한다. 대피소가 하나도 없으면 \(-1\)을 출력한다.
지점과 질의 수가 매우 크므로 각 질의마다 탐색하는 풀이는 통과할 수 없다. 센트로이드 분할로 각 센트로이드에 대해 가장 가까운 대피소까지 거리를 전처리하면 각 질의를 \(O(\log N)\) 개의 조상 센트로이드만 확인해 답할 수 있다.
\(1 \le N \le 100{,}000\)
\(0 \le M \le N\)
\(1 \le Q \le 100{,}000\)
\(1 \le w \le 10^6\)
\(1 \le a, b, q \le N\)
첫 줄에 \(N\), 대피소 수 \(M\), 질의 수 \(Q\)가 주어진다.
다음 \(N-1\)줄에 도로 정보 \(a\), \(b\), \(w\)가 주어진다.
그 다음 줄에 대피소가 설치된 지점 번호 \(M\)개가 공백으로 구분되어 주어진다 (\(M=0\)이면 이 줄은 비어 있다).
이어서 \(Q\)개의 줄에 각 질의 지점 \(q\)가 주어진다.
각 질의에 대해 가장 가까운 대피소까지의 거리(없으면 \(-1\))를 한 줄에 하나씩 출력한다.
4 2 3
2 1 1
3 1 4
4 3 2
2 4
1
3
4
1
2
0대피소는 2,4. 지점1->가장가까운건 2(거리1). 지점3->4(거리2). 지점4->자기자신(거리0).
4 0 2
2 1 2
3 2 2
4 3 2
1
4
-1
-1대피소가 없으므로 모든 질의에 -1.
riseoj 작성
출처 Original
평가 및 의견
가장 가까운 대피소
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 가까운 대피소