#658. [BJWC2012] 冻结

[BJWC2012] 冻结

题目描述

我们考虑最简单的旅行问题吧: 现在这个大陆上有 NN 个城市,MM 条双向的道路。城市编号为 11 ~ NN,我们在 11 号城市,需要到 NN 号城市,怎样才能最快地到达呢?

这不就是最短路问题吗?我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall 等算法来解决。

现在,我们一共有 KK 张可以使时间变慢 50%50\% 的 SpellCard,也就是说,在通过某条路径时,我们可以选择使用一张卡片,这样,我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是:

  1. 在一条道路上最多只能使用一张 SpellCard。
  2. 使用一张 SpellCard 只在一条道路上起作用。
  3. 你不必使用完所有的 SpellCard。

给定以上的信息,你的任务是:求出在可以使用这不超过 KK 张时间减速的 SpellCard 之情形下,从城市 11 到城市 NN 最少需要多长时间。

输入格式

第一行包含三个整数:NN、MM、KK。

接下来 MM 行,每行包含三个整数:AiA_i、BiB_i、TimeiTime_i,表示存在一条 AiA_i 与 BiB_i 之间的双向道路,在不使用 SpellCard 之前提下,通过它需要 TimeiTime_i 的时间。

输出格式

输出一个整数,表示从 11 号城市到 NN 号城市的最小用时。

样例

4 4 1 
1 2 4 
4 2 6 
1 3 8 
3 4 8 
7

题目来源:洛谷 P4822