4.最小花费

题目描述

有$n$个城市（编号为$0 \cdots n-1$），$m$条道路，经过每条道路有一个花费$v$。特别的是，现在可以让其中的最多$k$条道路花费为$0$。从城市$s$到城市$t$，求最小花费。

输入格式

第一行：三个整数$n$，$m$，$k$如题意所描述。

第二行：两个整数$s$，$t$代表出发城市和目标城市编号。

接下来$m$行：每行三个整数$x$，$y$，$v$代表$x$和$y$城市之间的高速公路收费为$v$元。

输出格式

共一行，输出一个整数，代表最少花费。

数据范围与提示

• 对于$10\%$的数据，$n \leq 100$，$k = 0$
• 对于$30\%$的数据，$n \leq 5$，$m \leq 10$，$k \leq 2$
• 对于$100\%$的数据，$n \leq 10000$，$m \leq 50000$，$k \leq 10$，$v \leq 10000$

样例

5 6 1 
0 4 
2 3 5 
0 1 15 
1 2 5 
3 4 5 
2 3 3 
0 2 1005

8

4 3 1 
1 3 
0 1 50 
1 2 30 
1 3 50

0