#ABC035D. 寻宝者
寻宝者
题目描述
给定 个城镇和 条单向道路。第 条道路从 指向 ,通行需要 分钟;在城镇 停留一分钟可获得 单位收益。
你在时刻 位于城镇 ,必须在时刻 位于城镇 。在这段时间中可以任意选择移动和停留,移动时没有收益,停留时按所在城镇的单位收益计算。
请计算最多能获得的总收益。可以始终留在城镇 ,不要求前往其他城镇。
输入格式
第一行输入三个整数 $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)$。
第二行输入 个整数 。
此后 行,每行输入三个整数 $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)$。
任意两条道路的有序端点对不同。图不保证强连通。
输出格式
输出一个整数,代表最大总收益。答案可能超过 位整数范围。
测试样例
2 2 5
1 3
1 2 2
2 1 1
6
样例 1 解释
去城镇 花 分钟,返回城镇 花 分钟,剩下 分钟在城镇 获取收益,共获得 。全部留在城镇 只能获得 ,因此答案为 。
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
子任务
第一组子任务占 分,保证 ;第二组子任务占 分,无额外限制。