문제1165--등산하기 어려운 산봉우리

1165: 등산하기 어려운 산봉우리

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

성준이는 연구실 추계 워크샵으로 산간 지역에 가게 되었다. 워크샵에서 교수님은 연구실 학생들에게 각각 산봉우리에 오르게 한 다음에, 각자 알아서 가장 가까운 산장으로 들어가라고 지시했다.
봉우리 중에 일부는 산장이 설치되어있고, 봉우리 사이에는 등산로가 개설되어 있다. 그리고 봉우리에는 고유 번호가 붙어있다.
등산로 노선망은 아래와 같은 조건으로 개설되어 있다.
  • 임의의 두 봉우리는 단방향 등산로로 연결된다.
  • 임의의 두 봉우리 사이에 등산로가 하나도 없을 수도 있고, 여러 등산로가 존재할 수도 있다.
  • 임의의 봉우리에서 산장이 설치된 산 봉우리로 갈 수 있는 경로가 최소한 하나 이상 존재한다.
임의의 산 봉우리 A에서 B까지의 “거리”는 등산로 노선망에서 A에서 출발해서 B로 갈 수 있는 최단 경로의 길이로 결정된다.
가장 늦게 산장에 들어온 학생에게는 한 학기 내로 논문 한 편을 써야 하는 벌칙이 주어질 수 있다. 그래서 성준이는 산장으로부터 가장 먼 봉우리를 피하고 싶다. 성준이를 위해 산장까지의 거리가 가장 먼 봉우리와 그 봉우리로부터 산장까지의 거리를 구해서 알려주자.
(문제가 잘 이해되지 않는 경우 아래의 도움말을 읽어주세요)

입력 설명

첫째 줄에는 테스트 케이스 T (1 <= T <= 10)가 주어진다.
둘째 줄에 산봉우리의 수 P (2 <= P <= 5,000), 등산로의 수 Q (1 <= Q <= 10,000), 산장의 수 R (1 <= R < P)이 주어진다. 산봉우리는 [1, P] 범위의 고유번호가 부여된다.
다음 Q개의 줄에 봉우리의 고유번호 A (1 <= A <= P), B (1 <= B <= P)와 등산로의 길이 C(1<= C <= 100,000)가 공백을 사이에 두고 주어진다. A와 B는 서로 다른 값만이 주어진다. A, B, C가 각각 2, 5, 10으로 주어지면, 2번 봉우리에서 5번 봉우리로 가는 등산로가 존재하며, 그 거리는 10이라는 것을 의미한다. 등산로는 양방향으로 통행이 불가능하고 단방향으로만 통행할 수 있음에 유의한다.
마지막 줄에는 산장이 있는 산봉우리의 고유번호가 R개 주어진다.

출력 설명

각 테스트 입력 마다, 산장까지 가는 “최단거리”가 가장 먼 산봉우리의 고유번호와, 산 봉우리에서 산장 사이의 거리를 공백으로 구분해서 출력한다.
만약 산장까지 가는 “최단거리”가 가장 먼 산 봉우리를 2곳 이상을 찾은 경우, 고유번호가 가장 작은 것을 출력한다.
모든 테스트 케이스에 대하여 정답은 반드시 주어진다.

입력 예시 Copy

1
8 11 3
1 2 4
1 3 5
1 3 12
2 3 5
8 2 9
5 8 6
2 4 20
3 4 10
3 6 16
6 4 15
7 6 3
4 6 8

출력 예시 Copy

1 15

도움




위 그림과 같이 산 봉우리 8개와 등산로 11개가 주어지고, 4, 6, 8번 산봉우리는 산장이 설치된 산봉우리로 주어졌다고 합시다.

먼저 산장이 없는 산봉우리에서 산장이 있는 각각의 산봉우리로 가는 최단 거리를 구해야 합니다. 위 그림의 오른쪽 표와 같이 정리할 수 있습니다. 표의 첫 번째 열 값들이 출발할 산봉우리 번호, 첫번째 행 값들이 도착할 산장 번호입니다.
다음으로 각 산봉우리에서 가장 가까운 산장까지의 거리를 찾아야 합니다. 그리고 1, 2, 3번 산봉우리는 4번 산장으로 가는 거리, 5번 산봉우리는 8번 산장으로 가는 산봉우리, 7번 산봉우리는 6번 산장으로 가는 거리가 가장 짧습니다. (표에서 노란색으로 표시)
가장 가까운 산장까지의 거리 중에서 가장 값이 큰 경우를 찾으면 정답이 됩니다. 예시에서는 1번 산봉우리에서 4번 산장으로 가는 거리 15가 가장 큰 값 중의 하나이며, 2번 산봉우리보다 1번 산봉우리가 고유 번호가 작으므로 정답은 “1 15”가 됩니다.

출처/분류