检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染.
译自 JOI 2014 Final T4"フクロモモンガ"
JOI 君能在其中的 MMM 对桉树之间直接飞行,在各对树木之间飞行所需的时间是固定的.当 JOI 君在树木之间飞行的时候,他离地面的高度会每秒下降 111 米.也就是说,如果 JOI 君现在离地高度是 hhh 米,在树木之间飞行需要 ttt 秒,那么飞行之后的离地高度就会变成 h−th-th−t 米.当 h−th-th−t 小于 000 或大于目标树木的高度时则不能飞行.
JOI 君还能沿着树的侧面上下移动,使得他的离地高度在 000 到当前所在树木高度的范围内变化.JOI 君每使自己的离地高度增加或减少 111 米都需要 111 秒的时间.
JOI 君要从 111 号树木上高度为 XXX 米的位置出发,到树木 NNN 的顶端(高度为 HNH_{N}HN  米的位置)去.他想知道为了达成这个目标所需时间的最小值.
给出各棵树木的高度,JOI 君能直接飞行的树木对和 JOI 君最初所在位置的高度,请求出到达树木 NNN 顶端所需时间的最小值.
输出到标准输出,仅一行一个整数,表示从树木 111 上高度为 XXX 米处移动到树木 NNN 顶端所需时间的最小值(单位:秒).如果不能到达目的地则输出 −1-1−1.
JOI 君无法从树木 111 飞到树木 222.
M≤3000M\le 3000M≤3000
1≤M≤3000001\le M\le 3000001≤M≤300000
1≤Hi≤1091\le H_i\le 10^91≤Hi ≤109
1≤Tj≤1091\le T_j\le 10^{9}1≤Tj ≤109 X=0X=0X=0
表格中的 HiTjH_i T_jHi Tj  满足:1≤i≤N1≤j≤M1\le i\le N 1\le j\le M1≤i≤N1≤j≤M.
所有数据满足 0≤X≤H10\le X\le H_10≤X≤H1 .
需要先向下爬到高度为 hv+wh_v + whv +w 的点才能从该边飞过,可以证明这是最优选择.
此种情况在加边时即可判定并丢弃这条边.
从树上某点开始飞行时,无法到达终点.
处理完上一种情况以后,树上一定存在一个高度,使得从该高度开始正好可以飞到下一个点的 000 米高处.
容易证明,先下降到高度为 www 的点再飞过该边是最优选择.
本题答案大小可能会超出 int 上界,因此需要使用 long long 存储.
喜欢这篇文章?为什么不考虑打赏一下作者呢?