3377. [NOI Online 2020 1st PJ]魔法

【题目描述】

C 国由 $n$ 座城市与 $m$ 条有向道路组成，城市与道路都从 $1$ 开始编号，经过 $i$ 号道路需要 $t_i$ 的费用。

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

注意：使用魔法只是改变一次的花费，而不改变一条道路自身的 $t_i$；最终的费用可以为负，并且一个城市可以经过多次（包括 $n$ 号城市）。

【输入格式】

输入的第一行有三个整数，分别代表城市数 $n$，道路数 $m$ 和魔法次数限制 $k$。 

第 $2$ 到第 $(m + 1)$ 行，每行三个整数。第 $(i + 1)$ 行的整数 $u_i, v_i, t_i$ 表示存在一条从 $u_i$ 到 $v_i$ 的单向道路，经过它需要花费 $t_i$。

【输出格式】

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

【样例输入1】

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

【样例输出1】

-8

【样例输入2】

2 2 2
1 2 10
2 1 1

【样例输出2】

-19

【样例解释】

样例 1 解释： 

依次经过 $1$ 号道路、$2$ 号道路、$3$ 号道路，并在经过 $1,2$ 号道路前使用魔法。 

样例 2 解释： 

依次经过 $1$ 号道路、$2$ 号道路、$1$ 号道路，并在两次经过 $1$ 号道路前都使用魔法。

【数据范围与提示】

本题共 $20$ 个测试点，各测试点信息见下表。

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

对于全部的测试点，保证： 

$1 \leq n \leq 100$，$1 \leq m \leq 2500$，$0 \leq k \leq 10^6$。

$1 \leq u_i, v_i \leq n$，$1 \leq t_i \leq 10^9$。

给出的图无重边和自环，且至少存在一条能从 $1$ 到达 $n$ 的路径。

【来源】

NOI Online 2020 第一场 入门组 Task 3