P13534 [OOI 2023] The way home / 回家的路

CF1801D

著名魔术师博里斯·布迪尼在 X 国旅行，这个国家共有 $n$ 个城市。不幸的是，他在编号为 $1$ 的城市遭遇了盗窃。现在，布迪尼需要踏上回家的旅程，目标是回到编号为 $n$ 的城市。 他打算乘坐飞机返家。全国共有 $m$ 个航班，第 $i$ 个航班从城市 $a_i$ 飞往城市 $b_i$，票价为 $s_i$ 卢布。要搭乘某个航班，布迪尼必须身处起点城市 $a_i$，并且手中至少有 $s_i$ 卢布（这些钱在登机时会被扣除）。 被盗后，他仅剩 $p$ 卢布。但他并未气馁！在任意城市 $i$，他都可以随时举办魔术表演，每场表演能赚 $w_i$ 卢布。 请帮助布迪尼判断，他是否能够回到家乡。如果可以，求出他至少需要举办多少场表演。

第一行包含四个整数 $n$、$m$、$p$ 和 $g$（$2 \le n \le 800$，$1 \le m \le 3000$，$0 \le p \le 10^9$，$0 \le g \le 6$），分别表示城市数量、航班数量、初始卢布数和测试组编号。 第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$1 \le w_i \le 10^9$），表示在每个城市举办一场表演能获得的收入。 接下来 $m$ 行，每行三个整数 $a_i$、$b_i$ 和 $s_i$（$1 \le a_i, b_i \le n$，$1 \le s_i \le 10^9$），表示第 $i$ 个航班的起点、终点和票价。

输出一个整数，表示布迪尼至少需要举办的表演场数。如果无法回家，输出 $-1$。

### 样例解释 在第一个样例中，布迪尼最优策略是在第一个城市举办 $4$ 场表演，此时他共有 $2 + 7 \times 4 = 30$ 卢布，然后依次乘坐 $1 \to 3 \to 2 \to 4$ 的航班，花费 $6 + 8 + 11 = 25$ 卢布。 在第二个样例中，布迪尼最优策略是在第一个城市举办 $15$ 场表演，飞到第 $3$ 个城市后再举办 $9$ 场表演，然后前往第 $4$ 个城市。 ### 评分说明 本题测试数据分为 6 组。只有通过某一组的全部测试点，且通过部分之前组的全部测试点后，才能获得该组分数。有些分组不要求通过样例测试点。**离线评测**表示该组的测试结果会在比赛结束后公布。 | 组别 | 分值 | $n$ | $m$ | $s_i$ | $w_i$ | 必须通过的组 | 备注 | |:----:|:----:|:---:|:---:|:-----:|:-----:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | -- | 样例测试点 | | 1 | 14 | -- | -- | -- | $w_i=1$ | -- | | | 2 | 13 | -- | $m = n - 1$ | -- | -- | -- | $a_i = i$，$b_i = i + 1$ | | 3 | 17 | $n \le 10$ | -- | -- | -- | 0 | | | 4 | 19 | $n \le 100$ | -- | $s_i \le 100$ | -- | 0 | | | 5 | 21 | $n \le 100$ | -- | -- | -- | 0, 3, 4 | | | 6 | 16 | -- | -- | -- | -- | 0--5 | **离线评测** |