#题面
#题目描述
译自 JOI 2014 Final T4「フクロモモンガ」
飞天鼠 JOI 君住着的森林里长着编号为 到 的 棵桉树。第 棵树的高度是 米。
JOI 君能在其中的 对桉树之间直接飞行,在各对树木之间飞行所需的时间是固定的。当 JOI 君在树木之间飞行的时候,他离地面的高度会每秒下降 米。也就是说,如果 JOI 君现在离地高度是 米,在树木之间飞行需要 秒,那么飞行之后的离地高度就会变成 米。当 小于 或大于目标树木的高度时则不能飞行。
JOI 君还能沿着树的侧面上下移动,使得他的离地高度在 到当前所在树木高度的范围内变化。JOI 君每使自己的离地高度增加或减少 米都需要 秒的时间。
JOI 君要从 号树木上高度为 米的位置出发,到树木 的顶端(高度为 米的位置)去。他想知道为了达成这个目标所需时间的最小值。
给出各棵树木的高度、JOI 君能直接飞行的树木对和 JOI 君最初所在位置的高度,请求出到达树木 顶端所需时间的最小值。
#输入格式
第一行包含三个以空格分开的整数 和 ,意义分别与题目描述中的 和 相同。
接下来 行中,第 行有一个整数 ,表示树木的高度是 米。
接下来 行中,第 行有三个以空格分开的整数 ,表示 IOI 君能花 秒的时间从 飞到 或从 飞到 。
对于任意 ,满足 且 。
#输出格式
输出到标准输出,仅一行一个整数,表示从树木 上高度为 米处移动到树木 顶端所需时间的最小值(单位:秒)。如果不能到达目的地则输出 。
#输入输出样例
样例输入 #1
5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20
样例输出 #1
110
样例解释 #1
下列是其中一种最优解:
- 沿着树木 向上爬 米。
- 从树木 飞到树木 。
- 从树木 飞到树木 。
- 从树木 飞到树木 。
- 沿着树木 向上爬 米。
样例输入 #2
2 1 0
1
1
1 2 100
样例输出 #2
-1
样例输出 #2
JOI 君无法从树木 飞到树木 。
样例输入 #3
4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10
样例输出 #3
100
#数据范围与约定
本题采用 Subtask 方式评测。
子任务编号 | 分值 | 数据范围 | 特殊性质 |
---|---|---|---|
1 | 25 分 | 无 | |
2 | 25 分 | ||
3 | 50 分 | 无 |
表格中的 满足:。
所有数据满足 。
#思路
可以使用最短路算法解决本题。
对于每条边,会有以下几种情况:
- 到达点的高度大于树顶高度。
需要先向下爬到高度为 的点才能从该边飞过,可以证明这是最优选择。 - 在飞行途中落地。
这种情况又细分为两种情况:- 从树顶开始飞行时,无法到达终点。
此种情况在加边时即可判定并丢弃这条边。 - 从树上某点开始飞行时,无法到达终点。
处理完上一种情况以后,树上一定存在一个高度,使得从该高度开始正好可以飞到下一个点的 米高处。
容易证明,先下降到高度为 的点再飞过该边是最优选择。
- 从树顶开始飞行时,无法到达终点。
- 能正常飞到终点。
正常计算即可。
本题答案大小可能会超出 int
上界,因此需要使用 long long
存储。
#代码
1 |
|