题目描述

高桥君是一名冒险者，正在穿越一片包含 $N$ 个城镇的大陆。

城镇编号为 $1$ 到 $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。

输入格式

第一行三个整数 $N, M, F$。

第二行 $N$ 个整数 $R_1, R_2, \ldots, R_N$。

接下来 $M$ 行，每行三个整数 $U_i, V_i, W_i$，表示一条道路。

输出格式

输出高桥君从城镇 $1$ 到达城镇 $N$ 时体力的最大值。如果无法到达城镇 $N$，输出 -1。

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

11

3 1 5
0 0 0
1 2 3

-1

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

103

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

200

2 1 0
1000 1000
1 2 1000

1000

数据范围

• $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 U_i < V_i \leq N$
• $1 \leq W_i \leq 1000$
• 任意两个城镇之间最多有一条道路
• 输入均为整数

提示

本题考查状态压缩DP。由于 $N \leq 10$，可以用一个 $N$ 位二进制数表示已访问的城镇集合。

设 $dp[mask][v]$ 表示已访问城镇集合为 $mask$，当前在城镇 $v$ 时的最大体力。

转移时，尝试从当前城镇 $v$ 移动到相邻城镇 $u$，更新状态。

时间复杂度 $O(2^N \cdot N^2)$，空间复杂度 $O(2^N \cdot N)$。

来源

AtCoder AWC 0052E