题解：AT_arc191_d [ARC191D] Moving Pieces on Graph

· · 题解

我们考虑刻画一下最优解长什么样。

首先显然地，最短路加次短路为一种选择，即使它们之间有重合的部分，只要存在未重合的部分，我们只需要让其中一方挑一个未重合的点等一等就行了。

然后我们考虑如果当前路径上有一个三度点，就相当于一条链上某个地方多出来一个叉：

那么我们也是挑一个棋子先到 u 等一下，然后另一个棋子沿着最短路过去，这个棋子再从 u 出来继续走，设最短路长度为 d，显然此时答案为 2d+2。

但是我们发现还有一种情况，既不存在次短路，三度点又在最短路外面：

此时我们发现也是可以的，因为外接的三度点可以让我们有两个位置暂存棋子，先让 A 走到点 u、B 走到点 v，此时中间没有障碍了 A 一路冲到目标点 t，B 再从 v 走回 s，假设从 s 到最近三度点的距离为 l，那么此时答案为 2d+4l+4。当然也有可能是 t 那里挂着一个三度点，基本同理。

以上三种情况就是全部有解的情况了，无解的情况也就是既不存在三度点又不存在次短路，对 s,t 各跑一遍单源最短路、s 跑一遍单源次短路，然后上面三种的长度取最小值即可。