← 返回题目列表

Codeforces · 1253/F

F. 廉价机器人

中文机器翻译题面 查看原题

给您一个简单、无向、连通、加权的图,其中包含 $$$n$$$ 个节点和 $$$m$$$ 边。

节点编号从 $$$1$$$ 到 $$$n$$$。正好有 $$$k$$$ 个中心(充值点),即节点 $$$1, 2, \ldots, k$$$。

我们考虑一个机器人移动到这个图中,其电池容量为 $$$c$$$,尚未由构造函数修复。在任何时候,电池都包含 $$$x$$$ 之间的整数能量 $$$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$$$ 行的第 $$$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$$$ 和 $$$v$$$ 之间有一条边,权重为 $$$w_i$$$。

保证给定的图是简单的(不存在自环,并且每对节点之间至多有一条边)并且连通。

接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le k$$$, $$$a_i \neq b_i$$$)。

输出

您必须输出 $$$q$$$ 行,其中第 $$$i$$$ 行包含一个整数:完成第 $$$i$$$ 任务所需的最小容量。

示例

输入 #1

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

输出 #1

12

输入 #2

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

输出 #2

38
15

注意

在第一个示例中,图是链 $$$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$$$