← 返回题目列表

AtCoder · awc0052_e

E. 冒险家的旅程

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

分数: 433 分

问题陈述

高桥是一名冒险家。他正在穿越一个包含 N 城镇。

的 N 城镇编号为 1 to N,并且有 M 连接城镇的道路。的 i道路双向连接城镇 U_i 和镇 V_i,并且沿着这条路行驶需要花费 W_i 耐力。

高桥的初始体力是 F。他从城镇开始 1 想要到达城镇 N.

各城镇 j 有一个有恢复价值的旅馆 R_j。当高桥访问一个城镇时 第一次,那个小镇的旅店恢复了 R_j 耐力。每个城镇仅应用一次此恢复 - 如果他访问同一个城镇两次或多次,则从第二次访问开始不会发生恢复。请注意,耐力没有上限(它可以通过恢复任意增长)。

镇 1 在出发时被视为首次访问。因此,高桥在迈出第一步之前的体力是 F + R_1.

高桥的移动是通过重复以下步骤来执行的:

  1. 高桥选择了一条与他当前所在城镇相连的道路。但是,他只能选择一条行驶成本为 (W_i) 小于或等于他当前的体力。如果没有道路满足这个条件,高桥就无法继续前进。
  2. 他沿着选择的道路行驶,他的体力减少了 W_i。他的体力正好达到这个水平也是可以接受的 0.
  3. 到达目的地城镇后,如果这是他第一次访问该城镇,旅馆的恢复值 R_j 被添加到他的耐力中。

高桥可以沿着同一条路行驶任意多次,也可以多次访问同一个城镇(但是,如上所述,每个城镇只能应用一次旅馆恢复)。

考虑高桥从城镇出发的所有可能方式 1 到镇 N,到达城镇后找到最大体力 N。这是到达城镇时的体力 N 是指应用上述步骤 3 后的耐力(如果城镇 N 第一次访问,镇上的旅馆恢复 N 也适用)。

如果无法到达城镇 N 无论他如何移动,输出 -1.

约束

  • 2 \leq N \leq 10
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 0 \leq F \leq 1000
  • 0 \leq R_j \leq 1000 (1 \leq j \leq N)
  • 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
  • 1 \leq W_i \leq 1000 (1 \leq i \leq M)
  • 至多有一条道路连接任意一对城镇
  • 所有输入值均为整数

输入

N M F
R_1 R_2 \ldots R_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 第一行包含 N 代表城镇数量, M 代表道路数量,以及 F 代表初始耐力,以空格分隔。
  • 第二行包含 R_1, R_2, \ldots, R_N 代表每个城镇的旅馆恢复值,以空格分隔。
  • 以下 M 行提供有关每条道路的信息。
  • 的 (2 + i)-th 行包含城镇 U_i, V_i 由 i第条路和体力消耗 W_i 用于沿着该路行驶,以空格分隔。

输出

一行输出高桥到达城镇时的最大体力 N 来自城镇 1。如果无法到达城镇 N 无论他如何移动,输出 -1.


示例输入 1

3 2 10
5 3 7
1 2 8
2 3 6

示例输出 1

11

示例输入 2

3 1 5
0 0 0
1 2 3

示例输出 2

-1

示例输入 3

5 6 10
5 100 3 2 8
1 2 12
1 3 5
2 3 8
2 5 10
3 4 3
4 5 3

示例输出 3

103

示例输入 4

8 10 50
10 20 30 40 50 15 25 100
1 2 30
1 3 40
1 6 35
2 3 25
3 4 20
3 8 80
4 5 15
5 8 10
6 7 20
7 8 30

示例输出 4

200

示例输入 5

2 1 0
1000 1000
1 2 1000

示例输出 5

1000