## TLE '17 Contest 1 P4 - Tempest

View as PDF

Points: 12 (partial)
Time limit: 1.4s
Memory limit: 256M

Author:
Problem type
A lot of big storms.

Warm air and cold air don't mix very nicely – because whenever they do, storms tend to follow. Your job, as a Turbulent Location Estimator, is to track their movement.

Air currents in your area can be mapped into nodes and air channels. Initially, there is one warm air body at node and one cold air body at node . Each channel connects two distinct nodes and with traverse time of . All channels are bidirectional and have a confined path. No two nodes will have more than one channel connecting them.

Air bodies naturally expand. So, they may intersect at nodes, or even on channels! Wherever this occurs, the present air bodies cannot pass through each other. However, if this occurs on a node that connects to other unoccupied channels, then the present air bodies can continue to spread to those channels simultaneously alongside each other.

You have been given queries, each asking for : the exact time when a storm occurs at a particular location. It is possible to reach any node from any other node. Have you got what it takes for the job?

#### Constraints

Note: It is possible to have .

,
,
,

#### Input Specification

The first line contains four spaced integers: , , , and .
The following lines each contain three spaced integers: , , and .

The next line contains integer . The following lines each contain two spaced integers: and .
If , then is the number of a node .
If , then is the number of a channel .
Channel numbers appear in order in the input, starting at .

#### Output Specification

For each query, output on its own line. Time starts at . If a storm does not exist at that location, output -1.
Your answer will be judged as correct if it is within an absolute error of .

#### Sample Input

7 7 1 3
1 2 6
1 5 7
2 3 6
2 6 5
3 4 1
4 5 3
5 7 8
5
1 2
1 5
1 6
2 2
2 4

#### Sample Output

6
-1
11
5.5
6

#### Explanation

The warm air body starts at node while the cool air body starts at node . They both spread to reach node at the same time, causing a storm there at . Then, they both simultaneously spread alongside each other to node at . Note that storms occur along the entire path of channel , so we take the earliest incidence time as (rounded from a time negligibly greater than ).

Meanwhile, the cool air body reaches node first, spreading to node and . It essentially blocks off the warm air body's path to node . Thus, both bodies of air directly collide on channel at .