Cheap Robot
Contest: Codeforces Round 600 (Div. 2)
Difficulty rating: 2500
Tags: binary search, dsu, graphs, shortest paths, trees

You're given a simple, undirected, connected, weighted graph with $$$n$$$ nodes and $$$m$$$ edges.

Nodes are numbered from $$$1$$$ to $$$n$$$. There are exactly $$$k$$$ centrals (recharge points), which are nodes $$$1, 2, \ldots, k$$$.

We consider a robot moving into this graph, with a battery of capacity $$$c$$$, not fixed by the constructor yet. At any time, the battery contains an integer amount $$$x$$$ of energy between $$$0$$$ and $$$c$$$ inclusive.

Traversing an edge of weight $$$w_i$$$ is possible only if $$$x \ge w_i$$$, and costs $$$w_i$$$ energy points ($$$x := x - w_i$$$).

Moreover, when the robot reaches a central, its battery is entirely recharged ($$$x := c$$$).

You're given $$$q$$$ independent missions, the $$$i$$$-th mission requires to move the robot from central $$$a_i$$$ to central $$$b_i$$$.

For each mission, you should tell the minimum capacity required to acheive it.

Input format:
The first line contains four integers $$$n$$$, $$$m$$$, $$$k$$$ and $$$q$$$ ($$$2 \le k \le n \le 10^5$$$ and $$$1 \le m, q \le 3 \cdot 10^5$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$, $$$1 \le w_i \le 10^9$$$), that mean that there's an edge between nodes $$$u$$$ and $$$v$$$, with a weight $$$w_i$$$.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes) and connected.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le k$$$, $$$a_i \neq b_i$$$).

Output format:
You have to output $$$q$$$ lines, where the $$$i$$$-th line contains a single integer : the minimum capacity required to acheive the $$$i$$$-th mission.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example, the graph is the chain $$$10 - 9 - 2^C - 4 - 1^C - 5 - 7 - 3^C - 8 - 6$$$, where centrals are nodes $$$1$$$, $$$2$$$ and $$$3$$$.

For the mission $$$(2, 3)$$$, there is only one simple path possible. Here is a simulation of this mission when the capacity is $$$12$$$.

- The robot begins on the node $$$2$$$, with $$$c = 12$$$ energy points.
- The robot uses an edge of weight $$$4$$$.
- The robot reaches the node $$$4$$$, with $$$12 - 4 = 8$$$ energy points.
- The robot uses an edge of weight $$$8$$$.
- The robot reaches the node $$$1$$$ with $$$8 - 8 = 0$$$ energy points.
- The robot is on a central, so its battery is recharged. He has now $$$c = 12$$$ energy points.
- The robot uses an edge of weight $$$2$$$.
- The robot is on the node $$$5$$$, with $$$12 - 2 = 10$$$ energy points.
- The robot uses an edge of weight $$$3$$$.
- The robot is on the node $$$7$$$, with $$$10 - 3 = 7$$$ energy points.
- The robot uses an edge of weight $$$2$$$.
- The robot is on the node $$$3$$$, with $$$7 - 2 = 5$$$ energy points.
- The robot is on a central, so its battery is recharged. He has now $$$c = 12$$$ energy points.
- End of the simulation.

Note that if value of $$$c$$$ was lower than $$$12$$$, we would have less than $$$8$$$ energy points on node $$$4$$$, and we would be unable to use the edge $$$4 \leftrightarrow 1$$$ of weight $$$8$$$. Hence $$$12$$$ is the minimum capacity required to acheive the mission.

—

The graph of the second example is described here (centrals are red nodes):

The robot can acheive the mission $$$(3, 1)$$$ with a battery of capacity $$$c = 38$$$, using the path $$$3 \rightarrow 9 \rightarrow 8 \rightarrow 7 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 5 \rightarrow 4 \rightarrow 1$$$

The robot can acheive the mission $$$(2, 3)$$$ with a battery of capacity $$$c = 15$$$, using the path $$$2 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow 3$$$

Example input:
10 9 3 1
10 9 11
9 2 37
2 4 4
4 1 8
1 5 2
5 7 3
7 3 2
3 8 4
8 6 13
2 3

Example output:
12

Example input:
9 11 3 2
1 3 99
1 4 5
4 5 3
5 6 3
6 4 11
6 7 21
7 2 6
7 8 4
8 9 3
9 2 57
9 3 2
3 1
2 3

Example output:
38
15

Editorial:
Key insight 1: Since we always end on a central, at any time our robot have to be able to reach the nearest central.
Key insight 2: Since we always start from a central, from any node $$$u$$$, going to the nearest central, then going back to $$$u$$$ can't decrease the number of energy points in the battery.
—
Firstly, let's do a multi-source Dijkstra from all centrals. We denote $$$d_u$$$ the distance from node $$$u$$$ to the nearest central.
Consider a fixed capacity $$$c$$$. Suppose that we're on node $$$u$$$ with $$$x$$$ energy points remaining in the battery. Note that $$$x \le c - d_u$$$.
If $$$x < d_u$$$, we can't do anything, the robot is lost because it can't reach any central anymore.
Otherwise, if $$$x \ge d_u$$$, we can go to the nearest central, then go back to $$$u$$$, hence we can always consider than $$$x = c - d_u$$$.
This is a simple but very powerful observation that allows us to delete the battery level in states explored. Hence, we can now solve the problem in $$$O(m \log m + qm \log n)$$$, doing binary search on answer and simple DFS for each query.
—
We need to optimize this solution. Now, reaching a node $$$u$$$ will mean reaching it with $$$x \ge d_u$$$.
During exploration of nodes, the necessary and sufficient condition for being able to reach node $$$v$$$ from $$$u$$$, through an edge of weight $$$w$$$, is that $$$(c - d_u) - w \ge d_v$$$, i.e. $$$d_u + d_v + w \le c$$$.
Hence, if we replace the weight of each edge $$$(u, v, w)$$$ by $$$w' = d_u + d_v + w$$$, the problem is reduced to find a shortest path from $$$a_i$$$ to $$$b_i$$$, in terms of maximum weight over edges used (which will be the capacity required by this path).
Solution 1 (offline):
Sort edges by new weight. Add them progressively, maintaining connexity with DSU.
As soon as two endpoints of a query become connected, we should put current capacity (i.e. new weight of the last edge added) as answer for this query.
To effeciently detect this, we can put tokens on endpoints of each query, and each time we do union (of DSU), we make tokens go up to the parent. If we do union by rank, each token will move at most $$$O(\log n)$$$ times.
Solution 2 (online):
Let's construct a MST of the new graph with Kruskal.
It is well-known that in this particular MST, for every pair of nodes $$$(u, v)$$$, the only path from $$$u$$$ to $$$v$$$ will be a shortest path (in terms of maximum weight over the path).
Hence we just have to compute the weight of paths in a tree, which can be done with binary lifting.
These two solutions both run in $$$O(m \log m + q \log n)$$$. Implementation of solution 1 is a bit shorter, but solution 2 can deal with online queries.
• Solution 1 (hugopm)
• Solution 2 (faremy)