NANO - Nanoworld
You're living in the future, way beyond the singularity and the exhaustion of ipv6, and you want to plan a fastest trip between your own planet and the planet of the your favourite restaurant.
You have a map of one-directional nanobot ferry lines between the planets in your system. The map states the distance dij between each (connected) pair of planets i and j, but due to the rapid technical evolution of this time, you estimate the travel time from i to j is dij/t where t is the time at which you choose to depart from i. (It is impossible to travel at t=0).
Input
The first line contains T the number of test cases.
The first line of each test case contains integers t0, N, M where
- t0 is the time at which you start your trip. 0 ≤ t0 ≤ 109
- N is the number of planets in your system, numbered 0...N-1. 0 < N ≤ 2.5*105
- M is the number of connections between planets. 0 < M ≤ 2.5*105
The following M lines of each test case contain integers i, j, d where
- i is the source planet. 0 ≤ i < N
- j is the destination planet. 0 ≤ j < N
- d is the distance from i to j. 0 ≤ d ≤ 109
Output
The arrival time at planet N-1 when starting at planet 0 at time t0, or "Impossible" (quotes for emphasis) if there is no possible route.
Example
Input: 2 0 5 5 0 2 2 2 3 3 3 4 4 0 1 5 1 4 6 0 2 1 1 1 0 Output: 4.91760625098 Impossible
hide comments
Antonio Roberto Paoli:
2018-11-17 02:55:56
If i=0 time is given, so I can't estimate it. In the first test case t0=0, but t=0 is not accepted because is impossible. The second paragraph need to be rewrite to make it clear, I think! |
|
Antonio Roberto Paoli:
2018-11-16 21:41:35
Thomas, could you please better explain dij/t? dist/time is velocity, so, time <> dist/time. Is this an interactive problem? Last edit: 2018-11-17 02:43:43 |
|
Thomas Dybdahl Ahle:
2017-12-16 23:58:57
It uses the standard Spoj judge for FP with 10^-2 absolute error. |
|
ppm:
2017-10-17 18:43:34
What's the expected output precision? |
Added by: | Thomas Dybdahl Ahle |
Date: | 2013-10-07 |
Time limit: | 1s-5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |