아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

관광

면접 대비

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

요약
1번 노드에서 각 목적지까지 경로에 포함된 가장 약한 도로가 최대한 강해지도록 경로를 선택합니다.
난이도

보통10점 중 5점

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

문제

도시 관광지를 노드, 도로를 양방향 간선으로 모델링한다. 각 도로에는 품질 값이 있고, 경로의 품질은 경로 위 간선 품질의 최솟값이다. 호텔은 노드 1이다. 각 목적지에 대해 노드 1에서 갈 수 있는 경로 중 경로 품질의 최댓값을 출력한다.

입력

첫 줄에 ,, , 가주어진다.다음가 주어진다. 다음 줄에 간선 ,, , 품질 (−−≤q≤100000 (-- \le q \le 100000)가 주어진다. 다음 줄에목적지줄에 목적지 ( e 1$)가 주어진다.

출력

각 목적지에 대해 달성 가능한 최고 경로 품질을 한 줄에 하나씩 출력한다.

제한

\le 500000,≤5000000, \le 5000000, \le V-1$

예제1

  1. 예제 1

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