Banikoara로 가는 가장 빠른 길
면접 대비시간 제한2초메모리 제한512 MB
마을들을 잇는 양방향 가중 도로가 주어질 때, 출발 마을에서 도착 마을까지의 최단 이동 거리를 구한다.
문제
Codjo: Banikoara로 떠날 준비가 됐어.
Bossi: Parakou를 지나서 가자.
Assiba: 아니야, Banikoara로 가는 가장 빠른 길은 Djougou를 지나는 길이야.
도시 사이를 잇는 도로의 목록과 각 도로의 길이가 주어진다. 도시 A에서 도시 B까지 이동하는 최단 거리를 구하는 프로그램을 작성하라.
도로는 양방향이다. 입력에 적힌 도로 한 줄은 어느 방향으로도 지날 수 있다. 두 도시를 잇는 도로가 여러 개일 수 있고, 양 끝이 같은 도시인 도로가 있을 수도 있다.
입력
첫째 줄에 데이터 집합의 개수 ()가 주어진다.
각 데이터 집합의 첫 줄에는 그 집합에 남은 줄의 수 (), 공백, 출발 도시의 이름, 공백, 도착 도시의 이름이 주어진다. 이어지는 개의 줄에는 도로가 하나씩 주어지며, 각 줄은 한쪽 도시의 이름, 공백, 다른 쪽 도시의 이름, 공백, 두 도시 사이의 거리(킬로미터)로 이루어진다.
거리는 이상 이하의 정수다. 도시 이름은 [a-z], [A-Z], 기호 "-"로 이루어진 길이 이하의 문자열이며, 대문자와 소문자를 구분한다. 출발 도시에서 도착 도시로 가는 경로는 항상 존재한다.
출력
각 데이터 집합마다 한 줄을 출력한다. 한 줄은 출발 도시의 이름, 공백, 도착 도시의 이름, 공백, 두 도시 사이의 최단 거리로 이루어진다.
출발 도시와 도착 도시가 같으면 최단 거리는 이다.