Racing Game#546
Vasya is creating a new racing simulation game. In the game, two players start at different points in a city, and the first player must reach one of the city exits while the second player tries to catch them in a race.
The first player's car can be faster than the second player's, but must be fast enough to guarantee reaching an exit. The second player's maximum speed is km/h.
The game's AI system must calculate the minimum speed that guarantees the first player can win. You are tasked with programming this AI system.
All roads can be considered infinitesimally narrow, and both cars are treated as point objects. If both players are ever at the same point (on any road or intersection) at the same time, the first player is caught and loses. Both cars start moving simultaneously and can accelerate or decelerate instantaneously to any speed up to their respective maximum speeds at any time. They can also change roads at intersections or reverse direction at any point on a road instantaneously, regardless of their current speed.
The first line contains three integers (2 \leq n \leq 100), (1 \leq m \leq 5000), and (1 \leq e \leq n), where is the number of intersections, is the number of roads in the city, and is the number of exits. The next lines each contain three integers , , (1 \leq a < b \leq n, 1 \leq l \leq 100), describing a road of length connecting intersections and . The next line contains integers in the range , describing the intersections connected to city exits. The last line contains two integers and (1 \leq b, p \leq n, b \neq p), specifying the starting intersections of the first and second players, respectively.
There is always a way to travel from any intersection to any other. Roads are only connected at intersections (although they may cross at other points using bridges or tunnels). Roads are bidirectional, and there cannot be more than one road between two intersections.
Output the minimum speed in km/h required for the first player to win, or the word IMPOSSIBLE if winning is impossible. In the first case, print the answer with an absolute error of 10^{-9}.
Example 1
Example 2
Example 3