这题实际上相当于在一条 $1$ ~ $n$ 的路径，找到两个点 $a, b$（先经过 $a$），使得 $w(b) - w(a)$ 最大。

可以用 SPFA 算法维护从节点 $1$ 到其它节点的点权值的最小值，以及节点 $n$ 到该节点的点权值的最大值，具体实现时候，用 $\min(min(u), w(v))$ 代替 $min(u) + w(v)$ 进行松弛就可以了。

最后枚举所有的节点，找到 $\displaystyle \max_{1 \le i \le n}(max(i) - min(i))$ 。