AT_joi2018ho_d 定期券 (Commuter Pass) 题解

题意：给定一张无向图 $G$，现在给定四个点 $S$，$T$，$u$，$v$，你需要任意选取 $S\to T$ 的一条最短路，并使得将其上所有边边权均赋为 $0$ 后 $u\to v$ 最短路长度最短。

题解：

首先考虑下面的引理：

$\textbf{Lemma}$ 图中 $S\to T$，$u\to v$ 可以构造两条最短路满足下列两种情况中至少一组：

• 两条图上的路径没有重边。
• 两条图上的路径有且只有一段相同的边。

$\textbf{Proof}$ 若上述两条图上的路径有两段或以上的重合部分，则任意两段相邻的重合部分，必然有一段路径不重合。考虑找出这一段路径在另一条最短路上所对应的路径，则此时若这条新的路径边权之和大于或等于原来最短路，则换为原来的最短路一定不会更劣；若小于原来的最短路，则原来的最短路就可以被替换为现在的路径，不符合最短路的定义。因此得证。

以及下面的另一个引理：

$\textbf{Lemma}$ 令 $\text{DS}$ 数组表示 $S$ 点为原点的最短路长度，$\text{DT}$ 数组表示 $T$ 点为原点的最短路长度，则对于每一条 $u\leftrightarrow v$，长度为 $w$ 的一条无向边，若满足 $\text{DS}_u+\text{DT}_v+w=\text{DS}_{T}$，或者 $\text{DT}_u+\text{DS}_v+w=\text{DS}_{v}$，则该边可能成为 $S\to T$ 的最短路，否则一定不可能。

$\textbf{Proof}$ 若 $\text{DS}_u+\text{DT}_v+w=\text{DS}_{T}$，则等式的前半部分可以分离为：

• 从 $S$ 沿最短路走到 $u$。
• 从 $u$ 走到 $v$，边权为 $w$。
• 从 $v$ 沿最短路走到 $T$。

而后半部分的 $\text{DS}_T$ 则表示 $S$ 直接走到 $T$ 的最短路。若这两个相等，则表示 $S\to u\to v\to T$ 这一条路径也为最短路，因此 $u\to v$ 这条边在最短路上。反过来同理。

若 $\text{DS}_u+\text{DT}_v+w>\text{DS}_T$，则根据类似于上面的分析可以发现，$u\to v$ 这条边在当前的选取路径下不在最短路上。而因为另外两个部分已经为最短的长度，没有其他的路径继续压缩上述的长度，因此她一定不在最短路上。因此证毕。

又有第三个引理：

$\textbf{Lemma}$ 若将所有可能在最短路上的边按照 $S\to T$ 最短路上的顺序建边，则新图为一张 $\text{DAG}$。

$\textbf{Proof}$ 若图不为 $\text{DAG}$ 则必然存在环。原图中不存在负权边，也就更不可能存在负环。没有负环就不会在新图中存在环，而有向无环图即为 $\text{DAG}$，因此得证。

因此建出新图 $G_1$ 和新图的反图 $G_2$，在 $G_1$ 中跑 $S$ 点的最短路，$G_2$ 中跑 $T$ 点的最短路。然后考虑枚举两条最短路重合的一段路径 $x\to y$，满足 $G_1$ 中 $x$ 可以到达 $y$，并且使得 $\text{DU}_x+\text{DV}_y$ 的值最小。此时考虑在 $\text{DAG}$ 上 $\text{dp}$，对于每一个点 $x$ 找出在 $G_1$ 中其能走到的 $y$ 中 $\text{DV}_y$ 的最小值。这个问题就是平凡的了。

于是这个题我们就做完啦！！！！！不愧是一道好题！！！