现在这个大陆上有 N 个城市,M 条双向的道路。城市编号为 1 ~ N,我们在 1 号城市,需要到 N 号城市,怎样才能最快地到达呢?
这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。
现在,我们一共有 K 张可以使时间变慢 50%的 SpellCard,也就是说,在通过某条路径时,我们可以选择使用一张卡片,这样,我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是:
给定以上的信息,你的任务是:求出在可以使用这不超过 K 张时间减速的 SpellCard 之情形下,从城市 1 到城市 N 最少需要多长时间。
第一行包含三个整数:N、M、K。
接下来 M 行,每行包含三个整数:A_i、B_i、Time_i,表示存在一条 A_i 与 B_i 之间的双向道路,在不使用 SpellCard 之前提下,通过它需要 Time_i 的时间。
输出一个整数,表示从 1 号城市到 N 号城市的最小用时。
4 4 1 1 2 4 4 2 6 1 3 8 3 4 8
7
样例 1 解释
在不使用 SpellCard 时,最短路为 1 \to 2 \to 4,总时间为 10。现在我们可以使用 1 次 SpellCard,那么我们将通过 2 \to 4 这条道路的时间减半,此时总时间为7。
对于 100\% 的数据,保证: