#658. [BJWC2012] 冻结
[BJWC2012] 冻结
题目描述
我们考虑最简单的旅行问题吧: 现在这个大陆上有 个城市, 条双向的道路。城市编号为 ~ ,我们在 号城市,需要到 号城市,怎样才能最快地到达呢?
这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall 等算法来解决。
现在,我们一共有 张可以使时间变慢 的 SpellCard,也就是说,在通过某条路径时,我们可以选择使用一张卡片,这样,我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是:
- 在一条道路上最多只能使用一张 SpellCard。
- 使用一张 SpellCard 只在一条道路上起作用。
- 你不必使用完所有的 SpellCard。
给定以上的信息,你的任务是:求出在可以使用这不超过 张时间减速的 SpellCard 之情形下,从城市 到城市 最少需要多长时间。
输入格式
第一行包含三个整数:、、。
接下来 行,每行包含三个整数:、、,表示存在一条 与 之间的双向道路,在不使用 SpellCard 之前提下,通过它需要 的时间。
输出格式
输出一个整数,表示从 号城市到 号城市的最小用时。
样例
4 4 1
1 2 4
4 2 6
1 3 8
3 4 8
7
题目来源:洛谷 P4822