P7242 - 「NOI2020」美食家

题目

P7242「NOI2020」美食家

限制 : 时间限制 : - MS 空间限制 : - KB

评测说明 : 2.0s,512MB

问题描述

坐落在 Bzeroth 大陆上的精灵王国击退地灾军团的入侵后，经过十余年的休养生息，重新成为了一片欣欣向荣的乐土，吸引着八方游客。小 W 是一位游历过世界各地的著名美食家，现在也慕名来到了精灵王国。

精灵王国共有 $n$ 座城市，城市从 $1$ 到 $n$ 编号，其中城市 $i$ 的美食能为小 W 提供 $c_i$ 的愉悦值。精灵王国的城市通过 $m$ 条单向道路连接，道路从 $1$ 到 $m$ 编号，其中道路 $i$ 的起点为城市 $u_i$，终点为城市 $v_i$，沿它通行需要花费 $w_i$ 天。也就是说，若小 W 在第 $d$ 天从城市 $u_i$ 沿道路 $i$ 通行，那么他会在第 $d + w_i$ 天到达城市 $v_i$。

小 W 计划在精灵王国进行一场为期 $T$ 天的旅行，更具体地：他会在第 $0$ 天从城市 $1$ 出发，经过 $T$ 天的旅行，最终在恰好第 $T$ 天回到城市 $1$ 结束旅行。由于小 W 是一位美食家，每当他到达一座城市时（包括第 $0$ 天和第 $T$ 天的城市 $1$），他都会品尝该城市的美食并获得其所提供的愉悦值，若小 W 多次到达同一座城市，他将获得多次愉悦值。注意旅行途中小 W 不能在任何城市停留，即当他到达一座城市且还未结束旅行时，他当天必须立即从该城市出发前往其他城市。

图 1：sample 1

对于上图，小 W 一种为期 $11$ 天的可行旅游方案为 $1\rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1$：

第 $0$ 天，小 W 从城市 $1$ 开始旅行，获得愉悦值 $1$ 并向城市 $2$ 出发。
第 $1$ 天，小 W 到达城市 $2$，获得愉悦值 $3$ 并向城市 $1$ 出发。
第 $4$ 天，小 W 到达城市 $1$，获得愉悦值 $1$ 并向城市 $2$ 出发。
第 $5$ 天，小 W 到达城市 $2$，获得愉悦值 $3$ 并向城市 $3$ 出发。
第 $7$ 天，小 W 到达城市 $3$，获得愉悦值 $4$ 并向城市 $1$ 出发。
第 $11$ 天，小 W 到达城市 $1$，获得愉悦值 $1$ 并结束旅行。
小 W 在该旅行中获得的愉悦值之和为 $13$。

此外，精灵王国会在不同的时间举办 $k$ 次美食节。具体来说，第 $i$ 次美食节将于第 $t_i$ 天在城市 $x_i$ 举办，若小 W 第 $t_i$ 天时恰好在城市 $x_i$，那么他在品尝城市 $x_i$ 的美食时会额外得到 $y_i$ 的愉悦值。现在小 W 想请作为精灵王国接待使者的你帮他算出，他在旅行中能获得的愉悦值之和的最大值。

输入格式

第一行四个整数 $n, m, T, k$，依次表示城市数、道路条数、旅行天数与美食节次数。

第二行 $n$ 个整数 $c_i$，表示每座城市的美食所能提供的愉悦值。

接下来 $m$ 行每行三个整数 $u_i, v_i, w_i$，依次表示每条道路的起点、终点与通行天数。

最后 $k$ 行每行三个整数 $t_i, x_i, y_i$，依次表示每次美食节的举办时间、举办城市与提供的额外愉悦值。

本题中数据保证：

对所有 $1\le i\le m$，有 $u_i \neq v_i$。但数据中可能存在路线重复的单向道路，即可能存在 $1\le i < j\le m$，使得 $u_i = u_j, v_i = v_j$。
对每座城市都满足：至少存在一条以该城市为起点的单向道路。
每次美食节的举办时间 $t_i$ 互不相同。

输出格式

仅一行一个整数，表示小 W 通过旅行能获得的愉悦值之和的最大值。

若小 W 无法在第 $T$ 天回到城市 $1$，则输出 $-1$。

样例输入 1

3 4 11 0
1 3 4
1 2 1
2 1 3
2 3 2
3 1 4

样例输出 1

样例输入 2

4 8 16 3
3 1 2 4
1 2 1
1 3 1
1 3 2
3 4 3
2 3 2
3 2 1
4 2 1
4 1 5
3 3 5
1 2 5
5 4 20

样例输出 2

样例输入 3

40 50 52501 0
23 389 517 534 664 801 1253 947 706 1961 1526 1117 11879 1521 437 2005 3247 1821 384 1311 16015 743 7014 3036 35 3694 2025 840 24487 10130 5207 436 3092 1118 4401 4484 1640 6677 1970 5548
1 2 1
2 3 4
3 4 5
4 5 4
5 6 5
6 7 3
7 8 4
8 9 3
9 10 1
10 11 1
11 12 1
12 13 3
13 14 2
14 15 1
15 16 5
16 17 4
17 18 5
18 19 1
19 20 5
20 21 1
21 22 3
22 23 2
23 24 3
24 25 1
25 26 4
26 27 4
27 28 5
28 29 1
29 30 2
30 31 3
31 32 2
32 33 5
33 34 5
34 35 4
35 36 2
36 37 5
37 38 4
38 39 2
39 40 3
40 1 1
17 28 1
20 14 3
20 14 4
21 26 2
24 11 4
9 30 4
1 16 3
14 33 2
7 12 4
12 23 5

样例输出 3

84079645

提示

样例解释 1

该样例为题目描述中的例子，最优旅行方案见题目描述。

样例解释 2

最优方案为 $1\rightarrow 3\rightarrow 4\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 1$。

第 $0$ 天，小 W 从城市 $1$ 开始旅行，获得愉悦值 $3$ 并沿道路 $3$ 通行。
第 $2$ 天，小 W 到达城市 $3$，获得愉悦值 $2$ 并沿道路 $4$ 通行。
第 $5$ 天，小 W 到达城市 $4$，由于美食节获得愉悦值 $20 + 4$ 并沿道路 $7$ 通行。
第 $6$ 天，小 W 到达城市 $2$，获得愉悦值 $1$ 并沿道路 $5$ 通行。
第 $8$ 天，小 W 到达城市 $3$，获得愉悦值 $2$ 并沿道路 $4$ 通行。
第 $11$ 天，小 W 到达城市 $4$，获得愉悦值 $4$ 并沿道路 $8$ 通行。
第 $16$ 天，小 W 到达城市 $1$，获得愉悦值 $3$ 并结束旅行。
小 W 获得的愉悦值之和为 $39$。

样例3满足 $k=0$

样例下载

对于所有测试点：

$1\le n\le 50$，$n\le m\le 501$，$0\le k\le 200$，$1\le t_i\le T\le 10^9$。

$1\le w_i\le 5$，$1\le c_i\le 52501$，$1\le u_i, v_i, x_i\le n$，$1\le y_i\le 10^9$。

每个测试点的具体限制见下表：

测试点编号	$n$	$m$	$T$	特殊限制
$1\sim 4$	$\le 5$	$\le 50$	$\le 5$
$5\sim 8$	$\le 50$	$\le 50$	$\le 52501$
$9\sim 10$	$\le 50$	$\le 50$	$\le 10^9$	A
$11\sim 13$	$\le 50$	$\le 50$	$\le 10^9$	$k=0$
$14\sim 15$	$\le 50$	$\le 50$	$\le 10^9$	$k\le 10$
$16 \sim 17$	$\le 50$	$\le 50$	$\le 10^9$
$18 \sim 20$	$\le 50$	$\le 501$	$\le 10^9$

特殊限制 A：$n = m$ 且 $u_i = i, v_i = (i \bmod n) + 1$。

测试点编号	\(n\)	\(m\)	\(T\)	特殊限制
$1\sim 4$	\(\le 5\)	\(\le 50\)	\(\le 5\)
$5\sim 8$	\(\le 50\)	\(\le 50\)	\(\le 52501\)
$9\sim 10$	\(\le 50\)	\(\le 50\)	\(\le 10^9\)	A
$11\sim 13$	\(\le 50\)	\(\le 50\)	\(\le 10^9\)	\(k=0\)
$14\sim 15$	\(\le 50\)	\(\le 50\)	\(\le 10^9\)	\(k\le 10\)
$16 \sim 17$	\(\le 50\)	\(\le 50\)	\(\le 10^9\)
$18 \sim 20$	\(\le 50\)	\(\le 501\)	\(\le 10^9\)