# 龜兔賽跑簡要題解

先把 $S-T$ 的最短路先求出來然後我們叫這條路徑為 $P$
你現在就只在乎把 $P$ 上面拔掉後的最短路是多少

為了方便先假設全點對最短路唯一

假設我們用個資料結構 維護一下 把$P$上第 $i$ 個點拔掉後的最短路

定義 $F(X)$ 為 走 $S\to X$ 最短路 會經過 $P$ 上最後面的一個點
$FD(X)$ 為 $S\to X$ 最短路長度
定義 $G(X)$ 為走 $T\to X$ 最短路 會經過 $P$ 上最前面的一個點
$GD(X)$ 為 $X\to T$ 最短路長度

那考慮以下三種狀況
1. $S\to A\to B\to T$
此時 $S\to A$ 會走最短路 且 $B\to T$ 會走最短路
並且 $A-B$ 恰為一條邊
如果我們直接枚舉 $A, B$
那這時候就可以更新 $(F(A), G(B))$ 區間為 $len(A, B) + FD(A) + GD(B)$

2. $S\to A\to T$
此時 $S\to A$ 會走最短路 且 $A\to T$ 會走最短路
那這時候可以更新 $(F(A), G(A))$ 區間為 $FD(A) + GD(A)$

3. 最後一個比較特別的狀況
考慮現在拔掉 $P$ 上第 $y$ 個點
那你發現唯一剩下的 case 就是
$S\to A$ 走不經過 $y$ 最短路
$A\to T$ 走不經過 $y$ 最短路
然後考慮 $F(A) = y, G(A) = y$
那就想辦法把所有點都跑去跑個最短路 對於 $i$ 得到 $S\to i$ 不經過 $F(i)$, 的最短路
和 $i\to T$ 不經過 $G(i)$ 的最短路 就可以解決這個 case

-----------------------

以下是證明為什麼 case 1, 2, 3 就會包含全部的 case

考慮候選路徑 $Q$ 為一條可能為最後答案的路徑

為了方便順便把點重新編個號

在 $P$ 上面第 $i$ 個點就改成編號 $i$
所以 $S$ 的編號是 $1$, $T$ 的編號是 $|P|$
並假設 $Q$ 是在拔掉 $y$ 點狀況下的候選路徑

那考慮邊 $(a, b)$ 為 $Q$ 上第一條非 以$S$為源點 的最短路徑樹上的邊
以及邊 $(c, d)$ 為 $Q$ 倒數第一條非 以T為源點 的最短路徑樹上的邊

那如果 $(a, b)$ 不存在的話 case 1 會處理到

這時候有些性質是可以用的

1. $F(b) \geq y$ 因為如果 $F(b) < y$ 那就沒什麼理由要走 $(a, b)$ 直接走 $S\to b$ 最短路再說就好
2. $G(c) \leq y$ 同理
3. $F(x) \leq G(x)$ 如果沒有的話會矛盾

那如果 $F(b) > y$ 或是 $G(c) < y$ 就會發現 case 1 會處理到

所以接下來只剩下 $F(b) = G(c) = y$ 而且
對於所有 $u$ 在路徑 $b-c$ 上面都會滿足 $F(u) = G(u) = y$ 的 case
不然就會被 case 1 處理到

那這個 case 就會在 case 3 被處理掉

----
最後就是在如果沒有 "全點對最短路唯一" 的狀況

唯一不同的是 $F(X)$ 變成了一個 set, $G(X)$ 也是
那這時候就發現 留下最小的 $F(X)$, 最大的 $G(X)$ 就足夠了