시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 6 3 18.750%

문제

11637번 한신이는 결국 당내 최고의원으로 선출되지 못하여, 이에 대한 모든 책임을 지고 의원직을 사퇴하여 인생의 새로운 재미를 찾기 위해 미국 동부로 모험을 떠났다. 한신이는 버지니아에 살고 있는 친구에게 차를 빌려서 제한된 기름으로 버지니아주 방방곳곳을 돌아다닐 계획을 세웠다. 친구를 통해 버지니아 각 지역의 가치를 알게 되어, 기름이 바닥나지 않는 선에서 출발지에서부터 도착지까지의 지역적 가치를 최대로 할 수 있는 경로를 찾아보기로 하였다. 

비록, 경로에 중복하여 방문하게 되는 도시가 있더라도 오직 재미를 위한 여행이기에 가치를 최대로 하는 것을 목표로 하며, 한번 방문한 도시는 중복되어 가치가 합산되지 않는다.

입력

맨 위 첫번째 줄에 입력되는 정수 c는 방문할수 있는 지역의 수를 의미하며 다음 c줄에는 각 지역의 이름과 그 지역의 가치가 주어진다. 

다음 줄에는 정수 m이 주어진다. m은 방문 할 수 있는 지역들 사이의 도로의 수를 의미하며, 다음 m줄에는 두 지역의 이름과 해당 도로의 길이를 나타낸다. 도로의 길이는 모두 정수로 입력되며 각 도로들은 양방향으로 통행이 가능하다.

다음 줄에 입력되는 정수 p는 테스트 케이스의 수를 의미한다. 다음 p줄에는 출발지,도착지 그리고 이동할 수 있는 최대 거리가 입력된다.

모든 입력은 공백으로 구분되며, 지역 이름내에 공백은 없다. 예를 들어 하나의 지역 이름이 ”Virginia Beach”와 같이 입력 되진 않는다.

출력

각 케이스에 대한 출력은 “Case x:” 형식으로 출력된다. 이때 x는 해당 케이스 번호를 의미하며, 같은 줄에 해당 케이스의 최적의 경로에 대한 가치의 합을 함께 출력한다. 이때 가치의 합은 출발지와 도착지 또한 포함한다. 다음 줄에는 출발지부터 도착지까지의 지역 이름을 방문할 순서대로 출력한다.

만약 제한된 기름으로 출발지에서 도착지까지의 방문할 수 있는 경로가 없다면 경로와 가치 대신 ”Not possible”를 출력한다.

문제에 대한 설명이 복잡하여 경로를 찾는데 있어서 이해가 다소 힘들수 있으니 아래 예제를 참고하여 보시기 바랍니다.

예제 입력

10
VirginiaBeach 4
Richmond 5
Charlottesville 10
Blacksburg -5
Roanoke 3
Fredericksburg 3
Danville 8
Harrisonburg 3
Lynchburg 7
Arlington 5
7
VirginiaBeach Richmond 90
Richmond Charlottesville 72
Charlottesville Lynchburg 65
Richmond Fredericksburg 75
Fredericksburg Arlington 40
Lynchburg Roanoke 30
Roanoke Blacksburg 20
3
VirginiaBeach Charlottesville 400
Charlottesville Lynchburg 75
VirginiaBeach Richmond 10

예제 출력

Case 1: 29
VirginiaBeach
Richmond
Charlottesville
Lynchburg
Roanoke
Lynchburg
Charlottesville
Case 2: 17
Charlottesville
Lynchburg
Case 3: Not possible

힌트