本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-15 08:57:51

Complete The Graph

• 枚举：每次将为零的边加上 $1$，可以证明总有一个时刻最短路为 $L$。显然有单调性，二分即可。

• 两边 Dijkstra：先把全部零边设成 $1$，然后跑一边最短路，设 $D = L- f(t)$。$D < 0$ 时显然无解。然后跑第二遍最短路，在跑的过程中，如果对于边 $(u, v)$ 如果有 $g(u) + w \lt f(v) + D$，就让 $w \gets f(y) + D - g(x)$。

上述方法实际上将所有 $s$ 到 $t$ 上的有零点的路径长度都改成了 $L$。

P2149 [SDOI2009] Elaxia的路线

对每一个源点和终点跑一遍最短路，然后建出一个由 $s_1$ 到 $t_1$ 的最短路 DAG。之后在这个 DAG 上跑一次拓扑，找最长的同时是 $s_2$ 到 $t_2$ 的最短路的边。