시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

“Tommy, there will be a programming contest here in Vice City. One of the coaches has
stolen a copy of the problem set. The chief judge wants it back. Take out the coach guy at his hotel and return the problems back. The address is taped under the phone. Do it now!”

Not a tough job for you, Tommy Vercetti! Getting the mission at the pay phone, you must head off the coach at WK Charriot Hotel before he leaves. You have to get there fast! Get there very fast indeed! Unfortunately, the vehicle you start with may not run fast enough. But there are some fixed locations in Vice City at which you can find certain vehicles, like Diaz’s Mansion where you can find an Infernus. This way, you may change your vehicle on your way to hotel several times. For example, in the first sample input, you ride from ‘PayPhone’ to ‘CarShowRoom’ on a ‘PCJ600’ and drive the rest of the path in a ‘HotRingRacer’. Don’t forget that it takes one minute each time you change your vehicle.

You are given the names of these locations in the city and the distances between each pair. At each location you can find a certain vehicle anytime you get there. Knowing the top speed of each vehicle, you want to find out the minimum time in which you can reach the hotel. For the sake of simplicity, assume that you always drive at top speed of your vehicle.

입력

The first line of the input contains a single integer t (1 ≤ t ≤ 20) which is the number of test cases in the input. Each test case has three parts. The first part consists of m lines (1 ≤ m ≤ 100) of the form ‘vehicle speed’ where vehicle is the unique name of a vehicle and speed is a positive integer giving the top speed of the vehicle measured in Km/h.

The next part of the test case identifies the locations in the city and is separated from the first part by exactly one blank line. It consists of n lines (2 ≤ n ≤ 500) of the form ‘location vehicle’ where location is the unique name of a location in the city and vehicle is the name of the vehicle available in that location. The list of locations always includes the starting location ‘PayPhone’ and the destination ‘WKCharriot’.

The third part of the test case identifies the roads between locations and is separated from the previous part by exactly one blank line. It consists of several lines of the form ‘loc1 loc2 distance’ indicating there is a (two-way) road of length distance between the locations loc1 and loc2. Distances are expressed in kilometers and are positive integers. The test case is terminated by a line containing a single asterisk character (*).

All names (for vehicles and locations) are strings of at most 100 letters and digits with no space characters and are considered case sensitive. Items in an input line are separated by one or more space characters. Also, there may be arbitrary leading or trailing blanks except in empty lines used as separators.

출력

For each test case, there is one line in the output containing the minimum time (in minutes) you need to travel from ‘PayPhone’ to ‘WKCharriot’, or the word ‘UNREACHABLE’ if the destination is unreachable from the starting point. Print the results as numbers with exactly three decimal digits after decimal point. That is, the possible decimal digits after the third one should be ignored, and if there are less than three digits after decimal point, zero digits should be printed for missing digits.

예제 입력

2

Infernus     280
Cheetah      285
PCJ600       250
Stallion     180
HotRingRacer 300

Mansion         Infernus
CarShowRoom     HotRingRacer
VicePort        Cheetah
NorthPointMall  Infernus
PayPhone        PCJ600
WKCharriot      Stallion

PayPhone       CarShowRoom    10
PayPhone       VicePort       15
VicePort       WKCharriot     20
CarShowRoom    Mansion        15
Mansion        WKCharriot     15
Mansion        NorthPointMall 5
NorthPointMall WKCharriot     5
*
Caddy        80
MrWhoopie    60
Stretch      120
CubanHermes  160
Voodoo       170

CherryPoppy  MrWhoopie
Mansion      Stretch
PayPhone     CubanHermes
LittleHaiti  Voodoo
WKCharriot   Caddy

PayPhone      CherryPoppy    10
CherryPoppy   LittleHaiti    15
Mansion       WKCharriot     20
*

예제 출력

8.400
UNREACHABLE

힌트