Road Planner#2567
An acyclic road network consists of unidirectional road segments (edges), each connecting two intersections (vertices) out of a total of intersections. The time required to travel on a road segment is always positive and depends linearly on the number of cars using the segment :
Here, a_S and b_S are two constants, expressed as single precision floating point numbers, describing the properties of road segment . The time required to cross an intersection is .
A number of cars must travel from vertex to vertex N - 1 in this road network. Each car chooses its route selfishly to minimize its own travel time, aware that all other cars are doing the same. You are to write a program that computes how many cars will travel on each possible path from the source to the destination, and the time required 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 describe the tests. Each test begins with a line containing the number of vertices, the number of edges, and the number of cars, separated by spaces. Then, each edge is specified in a separate line, containing the following space-separated fields: source vertex, destination vertex, a_S, and b_S.
For each test, output one line indicating the minimum time for any car to travel in the network, rounded down to the nearest integer.
Note: The first input consists of vertices and edges; cars must travel from vertex to vertex . To achieve the smallest travel time, the cars will choose one of the two possible paths (0-1-3) and (0-2-3) so that the number of cars is equal on both; hence, the minimum travel time is \lfloor 0.01 \cdot 2000 + 45.1 \rfloor = 65.
The second input is similar to the first, except for the addition of a zero-cost edge from vertex to vertex . In this case, all cars selfishly choose the path (0-1-2-3), and the minimum travel time is .
Example 1