23286번 - 허들 넘기

허들 국가대표를 꿈꾸는 연두는 그래프 위에서 허들 넘기를 연습하려고 한다. 연두가 연습할 그래프는 정점이 N개 있고, 간선이 M개 있다. 간선은 방향성이 있어, 1에서 2로 가는 길이 있더라도, 2에서 1로 가는 길은 없을 수도 있다. 간선 위에는 허들이 중간에 놓여 있고, 간선을 지나갈 때는 반드시 허들을 넘어야 한다.

연두는 연습을 T번 할 것이고, 각 연습마다 출발 정점과 도착 정점을 미리 정해놓았다. 연두가 힘들지 않게 연습을 하기 위해, 각 연습마다 출발 정점에서 도착 정점으로 가는 경로 중에서 가장 높이가 높은 허들의 높이가 최소가 되는 것을 찾아보자.

첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의 줄에는 연습의 정보 s, e가 한 줄에 하나씩 주어진다. s는 출발 정점, e는 도착 정점을 의미한다.

입력으로 주어진 연습 마다 한 줄에 하나씩 출발 정점에서 도착 정점으로 가는 경로 중 가장 높은 허들 높이의 최솟값을 출력한다. 만약 출발 정점에서 도착 정점으로 갈 수 없는 경우 -1을 출력한다.

• 1 ≤ N ≤ 300
• 1 ≤ M ≤ 25,000
• 1 ≤ T ≤ 40,000
• 1 ≤ u, v ≤ N
• u ≠ v
• 1 ≤ h ≤ 1,000,000
• 1 ≤ s, e ≤ N
• s ≠ e