Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 2.0 Seconds Memory Limit: 65536K

Total Runs: 3 Accepted Runs: 0

An acyclic road network is composed of unidirectional road segments (edges), each connecting
two intersections (vertices) out of a total of N intersections. The time necessary to travel on a
road segment is always positive and it depends linearly on the number of cars C using the
segment s:
T(s) = a_{S}C + b_{S}
a_{S} and b_{s} are two constants expressed as single precision floating point numbers, describing the
properties of road segment s. The time necessary to cross an intersection is 0.
A number of cars must travel from vertex 0 to vertex N-1 in this road network. Each car chooses
its route selfishly in order to reduce its own travel time; each car knows that all the other cars will
also selfishly choose their route. You are asked to write a program that computes how many
cars will travel on each of the possible paths from the source to the destination, and the time
needed to travel on those paths.

The input file contains several tests and is organized as follows. The first line contains the
number of tests. The following lines contain the specification of the tests. Each test contains on
the first line the number of vertices, the number of edges and the number of cars, separated by
whitespaces. After that, each edge is given on a separate line and contains the following fields
separated by spaces: source vertex, destination vertex, a_{S} and b_{S}

The output will contain one line for each test input, specifying the minimum time for any car to travel in the network, rounded down to the nearest integer.

2 4 4 4000 0 1 0.01 0 0 2 0 45.1 1 3 0 45.1 2 3 0.01 0 4 5 4000 0 1 0.01 0 0 2 0 45.1 1 3 0 45.1 1 2 0 0 2 3 0.01 0

65 80

Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz