P2991 [USACO10OPEN] Water Slides G

题目描述

给定一个有 $n$ 个点 $m$ 条边的带权有向图。

从 $1$ 号点走到 $n$ 号点，最多有 $k$ 次会在选边的时候选错，求在最倒霉的情况下（即每次选错都是当前往下的最差解）的最长路径长度。

输入格式

第一行三个整数 $n \ m \ k(2 \le n \le 5 \times 10^4,1 \le m \le 1.5 \times 10^5,1 \le k \le 10)$。

下来 $m$ 行，每行三个整数 $x \ y \ c$，表示一条从 $x$ 到 $y$ 长度为 $c$ 的有向边$(1 \le c \le 2 \times 10^9)$。

输出格式

一行一个整数，表示最长路径长度。

输入输出样例 #1

输入 #1

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

输出 #1

9