题目大意
有一幅 $n$ 个点 $m$ 条边的有向图,边有边权(代表通过所需时间),你在 $1$ 号点,女朋友在 $n$ 号点。
你可以选择在 $1$ 号点延迟任意时间之后,选定一条路线开始游走,一旦开始游走就不能停下来。你的女朋友会在时间区间 $[a,b]$ 中的任意一个实数时间点 call 你,你一旦被 call 就要马上过去 $n$ 号点,女朋友的等待时间就是她 call 了之后到你到达所用的时间。
求女朋友的最坏等待时间最小。
$n,m \le 10^5,\ \ 0 \le a \le b \le 10^{12}$,边权 $\le 10^6$
保证每个点至少有一条出边,即总是可以无限游走的。
6s