81 - ZOJ Monthly, July 2009 - B
Jouney to the Center of the Earth is one of the most exciting views in the park. It shows the formation and develop of the Earth and dinosaurs and the Ice Age can be seen in it. It is divided into n parts according to the variety periods of the Earth. There are roads connecting different parts and you can see all the parts as you walk along the roads.
However, we wanted to see more exciting views in the park and didn't want to stayed too long in this view. So we made some shortcuts that might save some time in transporting from one part to another. With the shortcuts, we could spend less time in visiting this view. However, the shortcuts were somehow illegal and we wanted to use as few as possible. Your task is to calculate how many shorcuts we had to use in the condition that we must leave the view within T minutes.
There are multiple cases (no more than 50). The first line of each test case contains an integer n, indicating the number of parts. (1 <= n <= 100) The parts are numbered from 1 to n. The second line contains an integer M, indicating the number of roads. Then M lines in the form "a b c" follow, which mean there is road between the a-th part and the b-th part and it costs c minutes to walk along it. Then an integer S and S lines follow, discpibing the shortcuts with the same way as the roads. The next contains two integers indicating the parts to which the entrance and the exit connecting. The last line contains one integer T, the time limit to visit the Journey to the Center of the Earth.(0 <= T <= 1000000000)
The roads and the shortcuts are all bidirectional. There is at most one road between any two parts. There is at most one shortcut between any two parts. The time cost of each road or shortcut do not exceed 1000000.
If it is possible to go to the exit in time, output the minimu number of shortcuts that should be used. Or output "Impossible" instead.
4 3 1 2 7 2 3 5 3 4 7 2 1 3 1 2 4 1 1 4 8 4 3 1 2 7 2 3 5 3 4 7 2 1 3 1 2 4 1 1 4 7 4 3 1 2 7 2 3 5 3 4 7 2 1 3 1 2 4 1 1 4 6
1 2 Impossible
Author: GUAN, Yao
Source: ZOJ Monthly, July 2009