CF1253F.Cheap Robot

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.

给你一个简单、无向、连通、带权图，包含 $n$ 个节点和 $m$ 条边。

节点编号为 $1$ 到 $n$。图中恰好有 $k$ 个中心节点（即充电点），它们是节点 $1, 2, \ldots, k$。

我们考虑一个在该图中移动的机器人，其电池容量为 $c$（尚未由构造器确定）。在任意时刻，电池中所含能量为整数 $x$，满足 $0 \le x \le c$。

只有当当前能量 $x \ge w_i$ 时，机器人才能遍历一条权重为 $w_i$ 的边，且该操作消耗 $w_i$ 单位能量（即 $x := x - w_i$）。

此外，当机器人到达某个中心节点时，其电池将被完全充满（即 $x := c$）。

你将收到 $q$ 个相互独立的任务；其中第 $i$ 个任务要求将机器人从中心节点 $a_i$ 移动到中心节点 $b_i$。

对每个任务，请输出完成该任务所需的最小电池容量。

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$).

第一行包含四个整数 $n$、$m$、$k$ 和 $q$（满足 $2 \le k \le n \le 10^5$，且 $1 \le m, q \le 3 \cdot 10^5$）。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $w_i$（满足 $1 \le u_i, v_i \le n$，$u_i \neq v_i$，$1 \le w_i \le 10^9$），表示节点 $u_i$ 与 $v_i$ 之间存在一条权重为 $w_i$ 的边。

保证所给图是简单图（无自环，且任意两个节点之间至多只有一条边）且连通。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（满足 $1 \le a_i, b_i \le k$，且 $a_i \neq b_i$）。

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.

你需要输出 $q$ 行，其中第 $i$ 行包含一个整数：完成第 $i$ 项任务所需的最小容量。

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$

在第一个例子中，图是一条链：$10 - 9 - 2^C - 4 - 1^C - 5 - 7 - 3^C - 8 - 6$，其中中心节点（centrals）为节点 $1$、$2$ 和 $3$。

对于任务 $(2, 3)$，仅存在一条简单路径。以下是当电池容量为 $12$ 时该任务的模拟过程：

• 机器人起始于节点 $2$，初始能量 $c = 12$；
• 机器人经过一条权值为 $4$ 的边；
• 机器人到达节点 $4$，剩余能量为 $12 - 4 = 8$；
• 机器人经过一条权值为 $8$ 的边；
• 机器人到达节点 $1$，剩余能量为 $8 - 8 = 0$；
• 机器人位于一个中心节点，因此电池被充满，当前能量变为 $c = 12$；
• 机器人经过一条权值为 $2$ 的边；
• 机器人到达节点 $5$，剩余能量为 $12 - 2 = 10$；
• 机器人经过一条权值为 $3$ 的边；
• 机器人到达节点 $7$，剩余能量为 $10 - 3 = 7$；
• 机器人经过一条权值为 $2$ 的边；
• 机器人到达节点 $3$，剩余能量为 $7 - 2 = 5$；
• 机器人位于一个中心节点，因此电池被充满，当前能量变为 $c = 12$；
• 模拟结束。

注意：若 $c$ 的值小于 $12$，则机器人在节点 $4$ 处的能量将少于 $8$，从而无法使用权值为 $8$ 的边 $4 \leftrightarrow 1$。因此，$12$ 是完成该任务所需的最小容量。

—

第二个例子的图结构如下所示（中心节点为红色节点）：

机器人可使用容量为 $c = 38$ 的电池，沿路径 $3 \rightarrow 9 \rightarrow 8 \rightarrow 7 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 5 \rightarrow 4 \rightarrow 1$ 完成任务 $(3, 1)$；
机器人可使用容量为 $c = 15$ 的电池，沿路径 $2 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow 3$ 完成任务 $(2, 3)$。