【NOI2020】美食家(加强版) 排行榜


时间限制: 2 s
空间限制: 524288 KB

题目来源

原题:【NOI2020】美食家

加强:saffah

数据规模与约定

除样例外共有 50 个测试数据,其中 $n=100, m=1000, k=10000, 1 \leq w_i \leq 100$。

其余数据范围与原题相同:$1 \leq t_i \leq T \leq 10^9, 1 \leq c_i \leq 52501, 1 \leq u_i,v_i,x_i \leq n, 1 \leq y_i \leq 10^9$。

数据都可以认为是在合法范围内均匀随机生成的。

问题描述

坐落在 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 不能在任何城市停留,即当他到达一座城市且还未结束旅行时,他当天必须立即从该城市出发前往其他城市。

此外,精灵王国会在不同的时间举办 $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$,依次表示每次美食节的举办时间、举办城市与提供的额外愉悦值。

本题中数据保证:

输出格式

输出到标准输出

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

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

样例

样例输入 1

样例输出 1

样例输入 2

样例输出 2

样例输入 3

样例输出 3


关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。




Judge Duck Online | 评测鸭在线
Server Time: 2020-09-25 02:07:49 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用