여행 경로 안내
면접 대비시간 제한1초메모리 제한128 MB
도시 쌍과 거리로 이루어진 양방향 가중 지도가 주어질 때, 각 질의 도시 쌍의 최단 경로를 찾아 구간별로 형식을 맞춰 출력한다.
문제
당신이 일하는 캘리포니아 자동차 클럽(CCC)은 회원들에게 여행 경로 안내 서비스를 제공하기로 했다. 출발지와 도착지로 이루어진 여러 쌍을 입력받아, 각 쌍의 두 도시를 잇는 최단 경로를 계산하는 프로그램을 작성하라. 각 여행에 대해 경로가 지나가는 모든 도시를 순서대로 나열하고, 각 구간의 도로 이름과 거리를 함께 보여 주는 보고서를 출력한다.
입력
입력은 두 부분으로 이루어진다.
첫 번째 부분은 고속도로 구간의 목록으로 주어지는 지도다. 각 구간은 쉼표로 구분된 네 개의 필드로 이루어진 한 줄로 표현된다.
- 첫째, 둘째 필드: 구간의 양 끝에 있는 두 도시의 이름 (각각 1–20자).
- 셋째 필드: 도로의 이름 (1–10자).
- 넷째 필드: 두 끝점 사이의 거리(마일)로, 양의 정수다.
모든 고속도로 구간은 양방향으로 통행할 수 있다. 구간 목록은 빈 줄로 끝난다.
두 번째 부분은 출발지와 도착지 쌍의 목록이며, 한 줄에 하나씩 출발지,도착지 형식으로 주어진다. 여기에 나오는 모든 도시는 지도에도 반드시 등장하며, 두 도시를 잇는 경로가 항상 존재한다. 이 목록은 입력의 끝까지 이어진다.
출력
각 쌍에 대해 입력에 주어진 순서대로 보고서를 하나씩 출력한다.
각 보고서는 다음으로 구성된다.
- 머리글 줄과 대시(-)로 된 줄
- 최단 경로의 각 구간마다 한 줄씩, 그 구간의 출발 도시, 도착 도시, 도로 이름, 거리를 나타낸다
- Miles 열 아래의 대시 줄과, 총 거리를 나타내는
Total줄
각 열은 고정 너비이며 한 칸의 공백으로 구분된다. From과 To 열은 너비 20이고 왼쪽 정렬, Route 열은 너비 10이고 왼쪽 정렬, Miles 열은 너비 5이고 오른쪽 정렬이다.
각 보고서 앞에는 빈 줄 두 개를 두되, 맨 첫 보고서 앞에는 빈 줄 하나만 둔다.
입력에는 불필요한 공백이 없다. 지도에는 도시가 최대 100개, 고속도로 구간이 최대 200개 있다. 각 최단 경로의 총 거리는 16비트 정수 범위에 들어간다. 모든 쌍에 대해 최단 경로는 유일하다.