#168. [JLOI2011] 飞行路线

[JLOI2011] 飞行路线

题目描述

Alice 和 Bob 现在要乘飞机旅行,他们选择了一家相对便宜的航空公司。该航空公司一共在 nn 个城市设有业务,设这些城市分别标记为 00n1n-1,一共有 mm 种航线,每种航线连接两个城市,并且航线有一定的价格。

Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市,途中可以进行转机。航空公司对他们这次旅行也推出优惠,他们可以免费在最多 kk 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少?

输入格式

第一行三个整数 n,m,kn,m,k,分别表示城市数,航线数和免费乘坐次数。

接下来一行两个整数 s,ts,t,分别表示他们出行的起点城市编号和终点城市编号。

接下来 mm 行,每行三个整数 a,b,ca,b,c,表示存在一种航线,能从城市 aa 到达城市 bb,或从城市 bb 到达城市 aa,价格为 cc

输出格式

输出一行一个整数,为最少花费。

5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
8

提示

数据规模与约定

对于 30%30\% 的数据,2n502 \le n \le 501m3001 \le m \le 300k=0k=0

对于 50%50\% 的数据,2n6002 \le n \le 6001m6×1031 \le m \le 6\times10^30k10 \le k \le 1

对于 100%100\% 的数据,2n1042 \le n \le 10^41m5×1041 \le m \le 5\times 10^40k100 \le k \le 100s,t,a,bn0\le s,t,a,b\le naba\ne b0c1030\le c\le 10^3

另外存在一组 hack 数据。