CF1253F Cheap Robot

给定一个简单的、无向、连通、带权图，有 $n$ 个节点和 $m$ 条边。 节点编号为 $1$ 到 $n$。有且仅有 $k$ 个“中心点”（充电点），即节点 $1, 2, \ldots, k$。 现在有一个机器人进入该图，电池容量为 $c$（$c$ 尚未确定）。任意时刻，电池中有 $x$ 单位的能量，$x$ 的取值范围为 $0$ 到 $c$（包含 $0$ 和 $c$）。 机器人只有在 $x \ge w_i$ 时才能通过权值为 $w_i$ 的边，并且通过该边会消耗 $w_i$ 单位能量（即 $x := x - w_i$）。 此外，每当机器人到达一个中心点时，电池会被完全充满（即 $x := c$）。 你将得到 $q$ 个独立的任务，第 $i$ 个任务要求机器人从中心点 $a_i$ 移动到中心点 $b_i$。 对于每个任务，你需要输出完成该任务所需的最小电池容量。

第一行包含四个整数 $n$、$m$、$k$ 和 $q$（$2 \le k \le n \le 10^5$，$1 \le m, q \le 3 \cdot 10^5$）。 接下来的 $m$ 行，每行包含三个整数 $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$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le k$，$a_i \neq b_i$）。

输出 $q$ 行，第 $i$ 行输出完成第 $i$ 个任务所需的最小电池容量。

在第一个样例中，图的结构为链 $10 - 9 - 2^C - 4 - 1^C - 5 - 7 - 3^C - 8 - 6$，其中中心点为节点 $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, 1)$，路径为 $3 \rightarrow 9 \rightarrow 8 \rightarrow 7 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 5 \rightarrow 4 \rightarrow 1$。 机器人可以用电池容量 $c = 15$ 完成任务 $(2, 3)$，路径为 $2 \rightarrow 7 \rightarrow 8 \rightarrow 9 \rightarrow 3$。 由 ChatGPT 4.1 翻译