TLE '17 Contest 1 P4 - Tempest

View as PDF

Submit solution

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

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 A_i and B_i with traverse time of C_i. 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 T_i: 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?


1 \le X, Y, A_i, B_i \le N \le 100\,000

N - 1 \le M \le \min\left(\frac{N(N - 1)}{2}, 200\,000\right)

1 \le C_i \le 5\,000

1 \le Q \le 300\,000

Note: It is possible to have X=Y.

Subtask Percentage Additional Constraints
1 10 M = \frac{N(N - 1)}{2}, C_i = 1
2 20 M = N - 1, X = Y
3 30 1 \le N \le 1\,000, F_i = 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: A_i, B_i, and C_i.

The next line contains integer Q. The following Q lines each contain two spaced integers: F_i and L_i.
If F_i = 1, then L_i is the number of a node (1 \le L_i \le N).
If F_i = 2, then L_i is the number of a channel (1 \le L_i \le M).
Channel numbers appear in order in the input, starting at 1.

Output Specification

For each query, output T_i 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

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
1 2
1 5
1 6
2 2
2 4

Sample Output



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.


There are no comments at the moment.