문제 링크
- http://icpc.me/16213
사용 알고리즘
- MST & HLD
- MSt & PBS
풀이
두 가지 풀이를 소개하겠습니다.
첫 번째 풀이는 단순히 Maximum Spanning Tree를 구한 뒤, HLD를 이용해 경로 최솟값 쿼리를 하는 것입니다. 크루스칼 알고리즘의 시간 복잡도 $O(M log M)$, HLD를 이용해 쿼리를 처리하는 시간 복잡도 $O(Q log^2 N)$, 총 $O(M log M + Q log^2 N)$ 시간에 문제를 풀 수 있습니다.
두 번째 풀이는 PBS를 이용하는 것입니다.
가중치가 X 이하인 간선만 이용해서 A에서 B로 갈 수 있는지 판단하는 방식으로 PBS를 돌릴 수 있습니다.