#ABC035D. 寻宝者

寻宝者

题目描述

\hspace{15pt}给定 nn 个城镇和 mm 条单向道路。第 ii 条道路从 uiu_i 指向 viv_i,通行需要 wiw_i 分钟;在城镇 ii 停留一分钟可获得 aia_i 单位收益。

\hspace{15pt}你在时刻 00 位于城镇 11,必须在时刻 tt 位于城镇 11。在这段时间中可以任意选择移动和停留,移动时没有收益,停留时按所在城镇的单位收益计算。

\hspace{15pt}请计算最多能获得的总收益。可以始终留在城镇 11,不要求前往其他城镇。

输入格式

\hspace{15pt}第一行输入三个整数 $n,m,t\left(2\leqq n\leqq10^5;\ 1\leqq m\leqq\min\{n(n-1),10^5\};\ 1\leqq t\leqq10^9\right)$。

\hspace{15pt}第二行输入 nn 个整数 a1,a2,…,an(1≦ai≦105)a_1,a_2,\dots,a_n\left(1\leqq a_i\leqq10^5\right)。

\hspace{15pt}此后 mm 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i;\ 1\leqq w_i\leqq10^5\right)$。

\hspace{15pt}任意两条道路的有序端点对不同。图不保证强连通。

输出格式

\hspace{15pt}输出一个整数,代表最大总收益。答案可能超过 3232 位整数范围。

测试样例

2 2 5
1 3
1 2 2
2 1 1
6

样例 1 解释

\hspace{15pt}去城镇 22 花 22 分钟,返回城镇 11 花 11 分钟,剩下 22 分钟在城镇 22 获取收益,共获得 2×3=62\times3=6。全部留在城镇 11 只能获得 55,因此答案为 66。

2 2 3
1 3
1 2 2
2 1 1
3
8 15 120
1 2 6 16 1 3 11 9
1 8 1
7 3 14
8 2 13
3 5 4
5 7 5
6 4 1
6 8 17
7 8 5
1 4 2
4 7 1
6 1 3
3 1 10
2 6 5
2 4 12
5 1 30
1488

子任务

\hspace{15pt}第一组子任务占 5050 分,保证 n≦200n\leqq200;第二组子任务占 5050 分,无额外限制。