#P4568. P4568 [JLOI2011] 飞行路线

P4568 [JLOI2011] 飞行路线

P4568 [JLOI2011] 飞行路线

普及+/提高 | 来源:JLOI2011 | 原题链接

题意

nn 座城市(编号 0∼n−10\sim n-1)、mm 条双向航线(价格 cc)。最多可免费乘坐 kk 次。求 s→ts\to t 的最少花费。

输入格式

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

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

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

输出格式

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

输入输出样例

样例 1 输入

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

样例 1 输出

8

数据范围

2≤n≤1042\le n\le 10^4,1≤m≤5×1041\le m\le 5\times10^4,0≤k≤100\le k\le 10,0≤s,t,a,b<n0\le s,t,a,b<n,aeba e b,0≤c≤1030\le c\le 10^3。

提示

考点:分层图 Dijkstra——状态是 ((城市,, 已用免费次数)),共 (k+1)⋅n(k+1)\cdot n 层。每条边两种转移:花钱 d+c 进同层、免费 d 进上一层。易错点:① 城市从 0 编号;② 免费次数用完就只剩花钱转移;③ 答案取终点在所有层的最小值;④ 与「反悔贪心」做法对比理解分层思想。

蜀ICP备2025119001号-1