만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

트럭

면접 대비

시간 제한2초메모리 제한512 MB

요약
가중치가 있는 무방향 그래프에서 두 정점 사이 경로의 최소 간선 가중치를 최대로 하는 값을 S개의 질의에 대해 각각 구한다.
난이도

보통10점 중 7점

유형
그래프, 최소 신장 트리, 유니온 파인드, 그리디
정답자
아직 제출이 없습니다

문제

Subtle Balloons Company(SBC)는 프로그래밍 대회에 풍선을 공급한다. 큰 공장과 창고를 운영하고, 트럭도 여러 대 보유한다.

Nlogonia에는 대회장이 많고, 모두 SBC에 풍선 배송을 맡겼다. Nlogonia는 여러 개의 다리로 이어진 군도다. 한 섬에 대회장이 여러 곳 있을 수 있고, SBC 창고도 여러 개 있을 수 있다.

배송 경로를 계획하다가 SBC는 문제에 부딪혔다. 안전을 위해 Nlogonia의 모든 다리에는 건너는 차량의 최대 무게 제한이 있다. 실어야 할 화물이 무거워서, SBC 운영 책임자는 창고에서 대회장까지 트럭이 실어 나를 수 있는 최대 무게를 구하는 프로그램을 요청했다.

입력

첫째 줄에 정수 NN, MM, SS가 주어진다. 각각 섬의 수, 섬을 잇는 다리의 수, 대회장의 수다. 섬에는 11번부터 NN번까지 번호가 붙어 있다.

다음 MM개 줄에는 다리 하나를 나타내는 정수 AA, BB, WW가 주어진다. 앞의 두 수는 그 다리가 잇는 두 섬의 번호이고, WW는 그 다리의 최대 허용 무게다. 단위는 톤이다.

모든 다리는 양방향으로 통행할 수 있다. 두 섬을 잇는 다리는 많아야 하나다. 다리만 이용해서 어느 섬에서든 다른 모든 섬으로 갈 수 있다. 가는 길에 다른 섬을 거쳐야 할 수도 있다.

다음 SS개 줄에는 대회장 하나를 나타내는 정수 LL과 HH가 주어진다. LL은 대회장이 있는 섬의 번호이고, HH는 그 대회장으로 풍선을 배송할 창고가 있는 섬의 번호다.

제한

  • 2≤N≤2×1042 \le N \le 2 \times 10^4
  • 1≤M≤1051 \le M \le 10^5
  • 1≤S≤5×1041 \le S \le 5 \times 10^4
  • 1≤A,B,L,H≤N1 \le A, B, L, H \le N, A≠BA \ne B, L≠HL \ne H
  • 0≤W≤1050 \le W \le 10^5

출력

입력에 주어진 순서대로 대회장마다 한 줄에 정수 하나를 출력한다. 창고에서 그 대회장까지 트럭이 실어 나를 수 있는 가장 큰 무게다.

트럭은 섬을 몇 개든 거쳐 갈 수 있다. 한 경로로 실어 나를 수 있는 무게는 그 경로에 있는 다리 제한 중 가장 작은 값이다.

예제6

  1. 예제 1

    입력
    4 5 4
1 2 9
1 3 0
2 3 8
2 4 7
3 4 4
1 4
2 1
3 1
4 3
    예상 출력
    7
9
8
7

  2. 예제 2

    입력
    4 5 2
1 2 30
2 3 20
3 4 10
4 1 40
2 4 50
1 3
1 2
    예상 출력
    20
40

  3. 예제 3

    입력
    2 1 1
1 2 0
1 2
    예상 출력
    0

  4. 예제 4

    입력
    2 1 1
2 1 100000
2 1
    예상 출력
    100000

  5. 예제 5

    입력
    4 4 4
1 2 1
1 3 9
3 4 9
4 2 9
1 2
2 1
1 4
3 2
    예상 출력
    9
9
9
9

  6. 예제 6

    입력
    6 5 5
1 2 5
1 3 7
1 4 100000
1 5 1
1 6 42
2 3
4 6
5 4
2 5
6 3
    예상 출력
    5
42
1
1
7