架设电话线

题目描述

有 $N$ 座通信基站和 $P$ 条双向电缆，第 $i$ 条电缆连接 $A_i,B_i$，升级费用为 $L_i$。需要选择一条从基站 $1$ 到基站 $N$ 的路径。其中至多 $K$ 条电缆可以免费升级，剩余电缆的收费等于其中最大的升级费用。求最小收费；若路径上的电缆都能免费升级，则收费为 $0$。

输入格式

第一行输入 $N,P,K$。接下来 $P$ 行，每行输入 $A_i,B_i,L_i$。

输出格式

输出最小收费；如果无法从 $1$ 到达 $N$，输出 $-1$。

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

4

说明与数据范围

$0\le K<N\le1000$，$1\le P\le2000$。一本通题面未注明电缆费用上限，本题包采用同源题 Telephone Lines 的范围 $1\le L_i\le10^6$；端点范围为 $1$ 到 $N$。原题来自 USACO 2008 Jan. Silver。

来源

ybt1496