오늘 티어 많이 올린듯 후후 JOI 국가의 행사 문제 링크 3가지 풀이가 존재한다고 한다. 참고 풀이 더보기 멀티소스 다익스트라로 전처리를 해준다. 각 노드 $v$에 대해 구한 최단거리를 $\text{value}[v]$라고 하자. 문제가 $\displaystyle \min _{\text{v}\in \text{경로}} \text{value}[v]$ 쿼리를 푸는 문제로 단순화된다. $\text{value}[v]$의 크기에 따른 크루스칼 변형을 떠올릴 수 있다. 그렇게 구성되는 스패닝 트리 위의 간선을 타는 경로가 최적이다. 따라서 구성된 스패닝 트리로 sparse table을 구성한다. 쿼리를 sparse table로 처리한다. 코드 더보기 구현이 워낙 길어져서, 모듈화시켜서 풀었다. 덕분에 디버깅 없이 1..