베시, 집으로 돌아오다
면접 대비시간 제한1초메모리 제한1024 MB
목장들을 잇는 가중치 있는 길이 주어졌을 때, 헛간 Z까지 가장 짧은 거리로 도착하는 소의 이름과 그 거리를 구합니다.
문제
소들이 각자 다른 목초지에 나가 있다. 저녁 식사 시간이 되자 Farmer John이 종을 울리고, 모든 소가 외양간을 향해 걷기 시작한다. 여러분이 할 일은 어느 소가 가장 먼저 외양간에 도착하는지 찾는 것이다. 제공되는 테스트 데이터에는 가장 빠른 소가 정확히 한 마리만 있다.
착유와 착유 사이에 각 소는 자기 목초지에 있다. 소가 없는 목초지도 있다. 각 목초지는 길로 하나 이상의 다른 목초지와 연결되어 있다. 외양간으로 가는 길이 있는 목초지가 하나 이상 있으므로, 모든 소는 외양간까지 가는 길이 있고 최단 경로를 안다. 소는 길을 어느 방향으로든 갈 수 있으며, 모든 소의 걷는 속도는 같다.
목초지는 'a'부터 'z', 그리고 'A'부터 'Y'까지 이름이 붙어 있다. 대문자 이름의 목초지마다 소가 한 마리씩 있다. 소문자 이름의 목초지에는 소가 없다. 외양간의 이름은 'Z'이지만, 외양간에는 소가 없다.
입력
1번째 줄: 정수 P (1 ≤ P ≤ 10000). 목초지(와 외양간)를 잇는 길의 개수.
2번째 줄부터 P+1번째 줄까지: 문자 두 개와 정수 하나. 앞의 두 항목은 연결된 목초지(또는 외양간)의 이름이고, 마지막 정수는 두 곳 사이의 거리이다.
- 1열: 첫 번째 목초지(또는 외양간)의 이름
- 2열: 공백
- 3열: 두 번째 목초지(또는 외양간)의 이름
- 4열: 공백
- 5열 이후: 정수 x (1 ≤ x ≤ 1000). 두 곳 사이의 거리
출력
한 줄에 두 가지 항목을 출력한다. 먼저 외양간에 가장 먼저 도착하는 소가 있는 목초지의 대문자 이름, 그다음 그 소가 이동한 길의 길이.