← 返回题目列表

Codeforces · 2110/D

D. 更少的电池

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

2077年,当机器人统治世界时,他们决定参加以下游戏。

有 $$$n$$$ 个检查点,第 $$$i$$$ 个检查点包含 $$$b_i$$$ 电池。最初,机器人在没有电池的情况下从第 $$$1$$$ 个检查点开始,并且必须到达第 $$$n$$$ 个检查点。

检查站之间总共有$$$m$$$单向通道。第 $$$i$$$ 通道允许从点 $$$s_i$$$ 移动到点 $$$t_i$$$ ($$$s_i \lt t_i$$$),但反之则不然。此外,只有当机器人至少有 $$$w_i$$$ 充电电池时才能使用第 $$$i$$$ 通道;否则,途中就会没电了。

当机器人到达 $$$v$$$ 点时,它还可以额外携带从 $$$0$$$ 到 $$$b_v$$$(含)之间的任意数量的电池。此外,它始终携带所有先前收集的电池,并且在每个检查点,它都会对所有先前收集的电池进行充电。

求机器人在旅程结束时可以拥有的最小电池数量,或者报告不可能从第一个检查点到达最后一个检查点。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 0 \leq m \leq 3 \cdot 10^5$$$)——分别是检查点的数量和通道的数量。

第二行包含 $$$n$$$ 数字 $$$b_i$$$ ($$$0 \leq b_i \leq 10^9$$$) — 第 $$$i$$$ 个检查点的电池数量。

接下来的 $$$m$$$ 行包含三个整数 $$$s_i, t_i, w_i$$$ ($$$1 \leq s_i \lt t_i \leq n, 1 \leq w_i \leq 10^9$$$) — 通道的端点以及通过通道所需的最小电池数量。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$。

保证$$$m$$$之和不超过$$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出旅程结束时可以拥有的最小电池数量,如果无法到达点 $$$n$$$,则输出 $$$-1$$$。

示例

输入
复制

4
3 3
2 0 0
1 2 1
2 3 1
1 3 2
5 6
2 2 5 0 1
1 2 2
1 3 1
1 4 3
3 5 5
2 4 4
4 5 3
2 0
1 1
4 4
3 10 0 0
1 2 1
1 3 3
2 3 10
3 4 5

输出
复制

1
4
-1
10

注意

在第一个测试用例中,您需要在起点处获取$$$1$$$电池,然后移动到点$$$2$$$,然后移动到点$$$3$$$。

在第二个测试用例中,您需要在起始点拿$$$2$$$电池,然后移动到点$$$2$$$,再拿$$$2$$$电池,移动到点$$$4$$$,然后移动到点$$$5$$$。

在第三个测试用例中,没有从点 $$$1$$$ 到点 $$$n$$$ 的路径。

在第四个测试用例中,您需要在起点处拿$$$1$$$电池,然后移动到点$$$2$$$,再拿$$$9$$$电池,移动到点$$$3$$$,然后移动到点$$$4$$$。