
ZOJ Problem Set  2864
The famous theif stole a valuable diamond in City S. He rushed to City T to leave this country as soon as he got the diamond. when he reach City T, he could fly to Country X where he would be safe.
Input There are multiple cases. The first line of each test case contains four intergers, n, m, indicating the number of cities and roads in the country, S, T, the starting city and the target city, 1 ≤ S, T ≤ n ≤ 1000. The following m lines contain 3 intergers each, indicating the two ending cities of the road and the time to pass the road. The cities are numbered from 1 to n and the time will not exceed 10000. There is at most one road between any two cities. All the roads are bidirectional. There is at least a path from City S to City T. The next line contains an integer q, and q lines containing an integer which is the time your leader inquires follow. q will be a positive integer no larger than 1000, and the time inquired will be nonnegative intergers no larger than 10000000.The time the theif got the diamond is the referrence time. Output Each test case outputs q integers corresponding to the quries. Output a blank line between test cases. Sample Input
4 4 1 4 Sample Output
1 Author: GUAN, Yao Source: ZOJ Monthly, June 2007 