귀가 > 문제은행

본문 바로가기


알고리즘 최단거리

1208 : 귀가

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 355 회    시도횟수: 1754 회   



농부 창호가 키우는 소들은 각자 자신의 목장에 얌전히 있다. 소가 없는 텅 빈 목장도 있다. 각각의 목장은 다른 목장들과 하나 혹은 더 많은 길로 연결이 되어 있다. 때때로 두 목장은 한 개 이상의 길로 연결되어 있을 수도 있으며, 적어도 한 개 이상의 목장들은 헛간으로 가는 길이 존재한다. 물론 소는 어떤 방향으로도 갈 수 있고, 모든 소들은 같은 속도로 걷게 된다.


목장들에는 'a' 부터 'z' 까지와, 'A' 부터 'Y' 까지로 번호가 붙여져 있다. 소 한 마리는 대문자 알파벳이 번호 매겨진 목장에 있다(목장 하나 당 소 한 마리 이다). 그리고 소가 없는 목장은 소문자로 번호가 매겨져 있다. 헛간은 그 헛간에 소가 있건 없건, 'Z' 로 번호가 매겨져 있다.


각각 목장과 목장, 혹은 목장과 헛간을 잇는 길의 거리가 주어질 때, 헛간으로 가장 먼저 올 수 있는 소와 그 거리를 구하는 프로그램을 작성하자.


첫째줄에는 P(1≤P≤10,000)개의 길 들이 입력된다. 둘째줄 부터 P+1 번째 줄까지, 한 줄에 두 문자와 숫자 하나가 입력 되는데, 이는 서로 연결 되는 두 목장(혹은 헛간)의 번호와, 그 길의 길이(1≤길이≤1,000)를 뜻한다.



가장 먼저 헛간에 도달하는 소가 원래 있던 목장의 번호와 그 소가 걷는 거리를 출력하라.


[Copy]
5 
A d 6 
B d 3 
C e 9 
d Z 8 
e Z 3
[Copy]
B 11


출처 : usaco



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.