龜兔賽跑簡要題解

先把 \(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)\) 就足夠了