TLE '17 Contest 1 P4 - Tempest

View as PDF

Submit solution


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 N nodes and M air channels. Initially, there is one warm air body at node X and one cold air body at node Y. Each channel connects two distinct nodes Ai and Bi with a traverse time of Ci. 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 Q queries, each asking for Ti: 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

1X,Y,Ai,BiN100000

N1Mmin(N(N1)2,200000)

1Ci5000

1Q300000

Note: It is possible to have X=Y.

Subtask Percentage Additional Constraints
1 10 M=N(N1)2, Ci=1
2 20 M=N1, X=Y
3 30 1N1000, Fi=1
4 40 No additional constraints.

Input Specification

The first line contains four spaced integers: N, M, X, and Y.
The following M lines each contain three spaced integers: Ai, Bi, and Ci.

The next line contains integer Q. The following Q lines each contain two spaced integers: Fi and Li.
If Fi=1, then Li is the number of a node (1LiN).
If Fi=2, then Li is the number of a channel (1LiM).
Channel numbers appear in order in the input, starting at 1.

Output Specification

For each query, output Ti on its own line. Time starts at 0. 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 0.1.

Sample Input

Copy
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

Copy
6
-1
11
5.5
6

Explanation

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

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


Comments

There are no comments at the moment.