
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. Input First line: two integers N, C, indicates the number of the sceneries and the number of the hotels. 1 <= N <= 100, 0 <= C <= NSecond 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*(N1) 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. Output For 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!" Sample Input 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 Sample Output 3 I will nerver go to that city! Author: YANG, Kete Source: ZOJ Monthly, February 2009 