【北京省选2012 冻结】

题目背景

BJOI2012 第一轮 DAY2 T1

题目描述

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

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

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

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

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

输入格式

第一行包含三个整数:N、M、K。
接下来 M 行,每行包含三个整数:Ai、Bi、Timei,表示存在一条 Ai 与 Bi 之间的双向道路,在不使用 SpellCard 之前提下,通过它需要 Timei 的时间。

输出格式

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

样例数据 1

输入

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

输出

7

样例数据 2

输入

3 3 1
1 2 6
2 3 6
1 3 14

输出

7

样例数据 3

输入

6 8 2
1 2 4
2 3 12
6 3 6
6 5 4
4 5 12
1 4 6
2 5 8
3 4 10

输出

10

备注

【样例1说明】
在不使用 SpellCard 时,最短路为 1→2→4 ,总时间为 10。现在我们可以使用 1 次 SpellCard,那么我们将通过 2→4 这条道路的时间减半,此时总时间为 7。

【样例2说明】
此时我们不选择原先的最短路 1→2→3,而直接从城市 1 走到城市 3 ,用唯一的一张 SpellCard 将所需时间减半。

【样例3说明】
一个最优解是:1→2→5→6,其中将 1→2、2→5 这两条边的时间减半。

【数据范围】
对于 30% 的数据:N,M≤10;
另有 30% 的数据:K=1;
对于100% 的数据:1≤K≤N≤50;M≤1000;1≤Ai,Bi≤N;2≤Timei≤2000;
为保证答案为整数,保证所有的 Timei 均为偶数;
所有数据中的无向图保证无自环、重边,且是连通的。

DP一遍,对于1~k的状态对每条边看是否用卡,用卡后是否更优,然后枚举0~k看不用卡是否更优,然后,裸SPFA。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*