Trafic
After they divided the country
into counties the monkeys have a new problem: they have to stop the banana traffic.
Monkey Land has N
cities numbered from 1
to N connected by
M two-directional roads. Between each two cities there is at most
one road but between any to cities there is at least one connecting path (made
up of one ore more roads). Cities 1
and N are capitals.
Lately, the banana traffic between the two capitals has increased. In order
to fight the traffic the president has G
soldiers he can place anywhere on a road, no matter how close to a city, but
not inside a city. In case of an attack on one of the capitals all soldiers
must get to that capital. Soldiers move at the same constant speed. The amount
of time required for such a mobilization is equal to the maximum distances from
the soldiers to one of the capitals.
Task
Write a program that finds a soldier placement solution so that any path from one capital to the other go through at least one road with a soldier and the mobilization time for the worst case scenario be minimal.
Input Data
Input
file trafic.in contains on the first line
three integers N M G
separated by blanks.
Each of the following M
lines contains three integers separated by blanks a
b c meaning "there is a two-way road between city a
and b of length c".
Output Data
Output file trafic.out will contain a single line with the minimum time needed for all the soldiers to get to a capital, written with one exact decimal. If there is no solution, the first line will contain -1.
Constraints
Example
|
trafic.in |
trafic.out |
6 6 2 1 2 1 2 3 2 3 6 1 1 4 1 4 5 3 5 6 1 |
2.5 |
Time limit: 0.15 seconds/test
Fechete Dan Ionut
University of Bucharest, Mathematics & IT Department
mailto:f_dany@eminem.com