대운하
시간 제한1초메모리 제한128 MB
간선마다 폭이 있는 그래프에서 최대 스패닝 트리를 이용해 두 도시 사이를 오갈 수 있는 배의 최대 폭을 K개의 질의에 대해 구합니다.
문제
대한민국에는 N개의 도시가 있고, 도시들을 잇는 M개의 양방향 운하를 만들려고 한다. 각 운하는 폭 w를 가지며, 배의 폭이 운하의 폭보다 작거나 같을 때만 그 운하를 통과할 수 있다.
정부는 K개의 운항 노선을 정했다. 각 노선은 두 도시 i와 j를 연결하며, 그 사이를 이동하는 배는 i에서 j까지 이어지는 어떤 경로 하나를 따라 모든 운하를 통과해야 한다. 가능한 경로가 여러 개라면 그중 하나를 선택할 수 있다.
배의 폭이 클수록 더 많은 승객을 태울 수 있으므로, 각 노선마다 운항 가능한 배의 폭의 최댓값을 구하라.
N개의 도시는 운하만으로 모두 서로 연결되어 있으며, 모든 운하는 양방향으로 통행할 수 있다.
입력
첫째 줄에 도시 수 N, 운하 수 M, 노선 수 K가 주어진다. (N <= 1000, M <= 100000, K <= 10000)
다음 M개의 줄에는 세 정수 i, j, w가 주어진다. 이는 도시 i와 도시 j 사이에 폭이 w인 양방향 운하가 있음을 의미한다. (1 <= i, j <= N, w <= 200)
다음 K개의 줄에는 각 노선이 연결하는 두 도시 i, j가 주어진다. (1 <= i, j <= N)
출력
K개의 줄에 걸쳐, 입력으로 주어진 각 노선마다 운항할 수 있는 배의 최대 폭을 순서대로 출력한다.