A dangerous trip
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 547
Solved: 119
- Description
- N cities are connected by a network of M one-way roads. It is known that these roads do not cross outside the cities. The numeration of the cities and the roads starts from 1.
One day, Haryy Potter must make a dangerous trip from city 1 to city N. Because there may have many monsters along the roads, he wants to finish this trip as soon as possible. Luckily, he knows a specil magic which can change the length of a road to half of the original length. But his magic is limited, and he can only use this magic once.
Now give you the network, try to find the minumum time he can finish this dangerous trip. - Input
- The first line contains an integer T,which means there are T test cases to be followed.
For each test case: the first line contains two integer n and m, which are the number of vertices and edges int the network.
Following the next m lines: each line describes an edge with three integers in the format: i, j, Cij.（cij is the time Haryy Potter must pay for from the city i to j if he don’t use magic）
(0 < n <= 104, 0 < m < 105, 0 < i, j <= n, 0 < cij < 105)
- Output
- For each test case, output the minimum time he must pay for this dangerous trip.
- sample input
-
2 4 4 1 2 8 1 3 6 2 4 18 3 4 20 4 4 1 2 8 1 3 6 2 4 18 3 4 21
- sample output
-
16 16.5
- hint
- source
- lshmouse