ZOJ Problem Set - 3166
Fat Murphy is really a lazy guy. When he goes out for sightseeing, only he cared about is to get back to the hotel which he stayed in as soon as possible. Taday is the Valentine's day, Fat Murphy's girl friend plans to make a tour of Hangzhou with him. Poor Murphy has to agree with that, or his girl friend will be really angry. As lazy as he was, he begins to collect information about Hangzhou for his own purpose. There are N sceneries in Hangzhou, and some of them are connected by a one way road. Besides, some of the sceneries have a hotel in it. Fat Murphy wants to choose a hotel to check in, when he goes out for sightseeing, he can get back to this hotel in a minimal time.
InputFirst line: two integers N, C, indicates the number of the sceneries and the number of the hotels. 1 <= N <= 100, 0 <= C <= N
Second line: C distinct integers represent the index of the scenery which has a hotel.
Third line: an integer M, indicates the number of the paths, 0 <= M <= N*(N-1)
The following M lines: each line contains threes integers: a, b, d, represents there is a road from a to b, and the time needed to pass this road is d. 1 <= d <= 1000
Process to the end of file.
OutputFor each case, output a single number represents the index of the hotel that Fat Murphy chooses.
If there is more than one optimal choice, just output the smallest one. If there is no choice, output "I will nerver go to that city!"
5 2 1 3 6 1 2 1 2 5 5 5 1 2 3 5 3 4 3 1 5 4 1 5 2 1 3 4 1 2 1 2 3 2 3 4 3 4 5 4
3 I will nerver go to that city!
Author: YANG, Kete
Source: ZOJ Monthly, February 2009