2.15

__ryp__ · 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 的最短路的边。