mengbierr

一个蒟蒻的博客

8月06

NWERC2018 Date Pickup

题目大意

给出一张图,R在1,J在n,J会在[a,b]时发出信号,R会在接到信号后直达n点,在此之前,R需要计划一条路线,在家等一段时间后出发,问J需要等候时间的最大值最小是多少。

题解

求出每个点到起点和终点的距离,二分答案w,将到起点+终点距离<=a+w的点标记为好的,如果一条边(u,v)中u是好的,且这条边长度+v到终点距离<=w,将v和这条边标记成好的,然后考虑所有好的边,如果这个图有环则合法,否则如果在图中停留时间长度>=b合法,否则不合法。
求图中停留时间长度:latest[i]表示在i点时的最长停留时间长度,初始时latest[i]=a+w-到终点距离,然后在新图中dp即可,latest[v]=max(latest[v],latest[u]+len)。
处理在家停留情况,需要在原图中加一条从1到1长度为0的边。

发表评论

电子邮件地址不会被公开。 必填项已用*标注