题目大意
有一张 $n$ 个点,$m$ 条边的有向图,其中每条边 $u\rightarrow v$ 都满足 $u<v$。
由 $1$ 号点出发,最初能量值为 $0$,每个点有一个值 $a_i$,经过该点时可增加处在范围 $[0,a_i]$ 内的能量值,经过每条边需要能量值不小于该边的权值 $w_i$。求到达 $n$ 点时的最小能量值。
(能量值只增不会衰减)
求最大值的最小值用二分!!!
第一感觉就是到一个点就把能加的能量值全加上,如果多了还可以减,但是不加满就可能后续的一些边走不了。
经过一定研究其实可以发现,答案就是经过路径中的边限制最大值。
所以二分边权最大值,在 checker
里只连上边权 $<= mid$ 的边,看是否可以连通。