67 - ZOJ Monthly, June 2008 - 1009
20008, Wormhole has been develpoed well. Beasts and Beauty Transportation Company get a task to transport some goods. They need your help to find the best path to complete the task.
In the unversity, human have built n transmission point, the goods is in transmission point s, and the task of Beasts and Beauty Transportation Company is to send them to transmission point t. Wormhole is a magic technology, if you travel from point u to point v if exists a tunnel between time. It can open the tunnel which may be considered as a straight line from point u to point v, so you can go along the tunnel in a short time. Because of the development of Wormhole, you can change the tunnel at the point of intersection of two tunnels. The rate of cost of engery in differnt tunnel may not be the same, the cost in tunnel i will be the rate ai multiply the length that travel in tunnel i. If you change the tunnel you will cost engery extraly |ai-aj|. Now you task it's to find the path that cost least energy.
The input cantains multiple test cases.
For each case, there are 4 integers in first line, n, m, s, t(n <= 50, m <= 50, 0 < s, t < n), as the problem statement says.
In the following n lines, every line contains 3 integer x, y, z; they are the coordinate of transmission point which are numbered from 0 to n-1 as order.
In the following m lines, every line contains 3 integer u, v, a, while means exists a tunnel between point u and point v. The rate of cost of engery is a.
Print the minimal energy cost for the transport in a single line, and keep two digits after radix point. If cannot transport, please print "Impossible!" instead.
You go to tunnel 0 from point 0, and change into tunnel 2 at the intersection(0.707,0.707) of tunnel 0 and tunnel 1, and then arrive point 1. In total you cost 0.707 * 1 + |1 - 1| + 0.707 * 1 = 1.41 energy.