## TRAFFIC LIGHTS- Return to The IOI'99 Competition
PROBLEM
In the city of Dingilville the traffic is arranged in an unusual way.
There are junctions and roads connecting the junctions. There is at most one road between
any two different junctions. There is no road connecting a junction to itself. Travel time
for a road is the same for both directions. At every junction there is a single traffic
light that is either blue or purple at any moment. The color of each light alternates
periodically: blue for certain duration and then purple for another duration. Traffic is
permitted to travel down the road between any two junctions, if and only if the lights at - the travel times for all roads (integers),
- the durations of the two colors at each junction (integers)
- and the initial color of the light and the remaining time (integer) for this color to change at each junction.
Your task is to find a path which takes the minimum time from a given source junction to a given destination junction for a vehicle when the traffic starts. In case more than one such path exists you are required to report only one of them. ASSUMPTIONS
- 2 <=
*N*<=300 where*N*is the number of junctions. The junctions are identified by integers 1 through*N*. These numbers are called id-numbers. - 1 <=
*M*<=14,000 where*M*is the number of roads. - 1 <=
*l*100 where_{ij}<=*l*is the time required to move from junction_{ij}*i*to*j*using the road that connects*i*and*j*. - 1 <=
*t*100 where_{ic}<=*t*is the duration of the color_{ic}*c*for the light at the junction*i*. The index*c*is either*B*for*blue*or*P*for*purple.* - 1 <=
*r*where_{ic}<= t_{ic }*r*is the remaining time for the initial color_{ic}*c*at junction*i.*
INPUT
The input is a text file named - The first line contains two numbers: The id-number of the source junction and the id-number of the destination junction.
- The second line contains two numbers:
*N*,*M*. - The following
*N*lines contain information on*N*junctions. The (*i+*2)’th*i*:*C*,_{i}*r*,_{ic}*t*,_{iB}*t*where_{iP}*C*is either ‘B_{i}*’*or ‘P*’*, indicating the initial color of the light at the junction*i.* - Finally, the next
*M*lines contain information on*M*roads. Each line is of the form:*i*,*j, l*where_{ij }*i*and*j*are the id-numbers of the junctions which are connected by this road
OUTPUT
The output must be a text file named If a - The first line will contain the time taken by a minimum-time path from the source junction to the destination junction.
- Second line will contain the list of junctions that construct the minimum-time path you have found. You have to write the junctions to the output file in the order of travelling. Therefore the first integer in this line must be the id-number of the source junction and the last one the id-number of the destination junction.
If a
- A single line containing only the integer 0.
EXAMPLE
EVALUATION
Your program will be allowed to run 2 seconds. |