#P3072. [NOI Online #1 入门组] 魔法

    ID: 1214 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划图论倍增最短路dp2020矩阵加速矩阵优化NOI Online

[NOI Online #1 入门组] 魔法

题目描述

C 国由 nn 座城市与 mm 条有向道路组成,城市与道路都从 11 开始编号,经过 ii 号道路需要 tit_i 的费用。

现在你要从 11 号城市出发去 nn 号城市,你可以施展最多 kk 次魔法,使得通过下一条道路时,需要的费用变为原来的相反数,即费用从 tit_i 变为 ti-t_i。请你算一算,你至少要花费多少费用才能完成这次旅程。

注意:使用魔法只是改变一次的花费,而不改变一条道路自身的 tit_i;最终的费用可以为负,并且一个城市可以经过多次(包括 nn 号城市)。

输入格式

输入的第一行有三个整数,分别代表城市数 nn,道路数 mm 和魔法次数限制 kk

22 到第 (m+1)(m + 1) 行,每行三个整数。第 (i+1)(i + 1) 行的整数 ui,vi,tiu_i, v_i, t_i 表示存在一条从 uiu_iviv_i 的单向道路,经过它需要花费 tit_i

输出格式

输出一行一个整数表示最小的花费。

4 3 2
1 2 5
2 3 4
3 4 1

-8
2 2 2
1 2 10
2 1 1

-19

提示

输入输出样例 1 解释

依次经过 11 号道路、22 号道路、33 号道路,并在经过 1,21,2 号道路前使用魔法。

输入输出样例 2 解释

依次经过 11 号道路、22 号道路、11 号道路,并在两次经过 11 号道路前都使用魔法。

数据规模与约定

本题共 2020 个测试点,各测试点信息见下表。

测试点编号 nn \leq mm \leq kk \leq 无环
121 \sim 2 55 2020 00 不保证
343 \sim 4 1010 5050
565 \sim 6 00
787 \sim 8 2020 200200 5050
9109 \sim 10 00 不保证
111211 \sim 12 100100 5050
131413 \sim 14 不保证
151815 \sim 18 25002500 10001000
192019 \sim 20 10610^6

对于【无环】一栏为“是”的测试点,保证给出的图是一张有向无环图,否则不对图的形态做任何保证。

对于全部的测试点,保证:

  • 1n1001 \leq n \leq 1001m25001 \leq m \leq 25000k1060 \leq k \leq 10^6
  • 1ui,vin1 \leq u_i, v_i \leq n1ti1091 \leq t_i \leq 10^9
  • 给出的图无重边和自环,且至少存在一条能从 11 到达 nn 的路径。

**民间数据使用 CYaRon 在 5 分钟内生成。如果发现数据有问题,请在讨论版发帖或私信

/user/22030