5593 - 提高:图论:最短路问题:分层图: 旅行问题
Time Limit : 1 秒
Memory Limit : 256 MB
现在这个大陆上有 个城市, 条双向的道路。城市编号为 ~ ,我们在 号城市,需要到 号城市,怎样才能最快地到达呢?
这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。
现在,我们一共有 张可以使时间变慢 50%的 SpellCard,也就是说,在通过某条路径时,我们可以选择使用一张卡片,这样,我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是:
- 在一条道路上最多只能使用一张 SpellCard。
- 使用一张SpellCard 只在一条道路上起作用。
- 你不必使用完所有的 SpellCard。
给定以上的信息,你的任务是:求出在可以使用这不超过 张时间减速的 SpellCard 之情形下,从城市 到城市 最少需要多长时间。
Input
第一行包含三个整数:、、。
接下来 行,每行包含三个整数:、、,表示存在一条 与 之间的双向道路,在不使用 SpellCard 之前提下,通过它需要 的时间。
Output
输出一个整数,表示从 号城市到 号城市的最小用时。
Examples
Input复制
4 4 1 1 2 4 4 2 6 1 3 8 3 4 8
Output复制
7
Hint
样例 1 解释
在不使用 SpellCard 时,最短路为 ,总时间为 10。现在我们可以使用 1 次 SpellCard,那么我们将通过 这条道路的时间减半,此时总时间为7。
对于 的数据,保证:
- ,。
- ,。
- 为保证答案为整数,保证所有的 均为偶数。
- 所有数据中的无向图保证无自环、重边,且是连通的。