#P4568. P4568 [JLOI2011] 飞行路线
P4568 [JLOI2011] 飞行路线
P4568 [JLOI2011] 飞行路线
普及+/提高 | 来源:JLOI2011 | 原题链接
题意
座城市(编号 )、 条双向航线(价格 )。最多可免费乘坐 次。求 的最少花费。
输入格式
第一行三个整数 ,分别表示城市数,航线数和免费乘坐次数。
接下来一行两个整数 ,分别表示他们出行的起点城市编号和终点城市编号。
接下来 行,每行三个整数 ,表示存在一种航线,能从城市 到达城市 ,或从城市 到达城市 ,价格为 。
输出格式
输出一行一个整数,为最少花费。
输入输出样例
样例 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
数据范围
,,,,,。
提示
考点:分层图 Dijkstra——状态是 城市 已用免费次数,共 层。每条边两种转移:花钱 d+c 进同层、免费 d 进上一层。易错点:① 城市从 0 编号;② 免费次数用完就只剩花钱转移;③ 答案取终点在所有层的最小值;④ 与「反悔贪心」做法对比理解分层思想。