兩種想法

1. 做兩次最短路

假設要從S走到E

設想一個路徑有通過一個邊 E(X, Y, T)，我們可以把花費時間拆成三個部分：
cost(S, E) = cost(S, X) + cost(X, Y) + cost(Y, T) = cost(S, X) + T + cost(Y, T)
如果對此邊使用裝置，那麼意思就是 T=0，上述等式就會變成
cost(S, E) = cost(S, X) + cost(Y, T)

對於每個邊，都算一次 cost(S, X) + cost(Y, T)，最小的那個就是所求

由於本題的圖是無向的，對 S 與 T 分別跑一次最短路，就可以求出所有的 cost(S, X) 與 cost(Y, T)=cost(T, Y)

如果遇到有向圖，則可先將原圖的所有邊都轉向(A→B變成B→A，即每個邊的起點終點對調)，得到反向的圖G'，對G'上的T做最短路，得出的 cost(T, Y) 既代表反向圖G'上從T到Y的最短路，也代表原圖G上從Y到T的最短路 (此結果的正確性不在此證明，可以自己想想or查網路)

2. 疊圖

建圖時，對於每顆正常星星A，我們額外多存一顆「疊加星星」A'

對兩顆星星 u, v，我們令從正常星星 u 移動到疊加星星 v' 的意義，代表從u移到v時使用了裝置，讓穿越時間變成0

於是建邊時，對於每個邊(X, Y, T)，除了多加(Y, X, T)外(因為是無向圖)，再額外建立四個邊(X, Y', 0)、(Y, X', 0)、(X', Y', T)、(Y', X', T)

對這個疊了兩層的圖正常跑最短路，所求即為 cost(X, Y')

如果圖共有N顆星星，你可以把編號A的疊加星星A'的編號設為A+N

兩種想法

1. 做兩次最短路

...

想法 1. 有些代號弄錯了，於是重寫一遍。

.....

假設要從A走到B

設想一個路徑有通過一個邊 (X, Y, T)，我們可以把花費時間拆成三個部分：
cost(A, B) = cost(A, X) + cost(X, Y) + cost(Y, B) = cost(A, X) + T + cost(Y, B)
如果對此邊使用裝置，那麼意思就是 T=0，上述等式就會變成
cost(A, B) = cost(A, X) + cost(Y, B)

對於每個邊，都算一次 cost(A, X) + cost(Y, B)，最小的那個就是所求

由於本題的圖是無向的，對 A 與 B 分別跑一次最短路，就可以求出所有的 cost(A, X) 與 cost(Y, B)=cost(B, Y)

如果遇到有向圖，則可先將原圖的所有邊都轉向(A→B變成B→A，即每個邊的起點終點對調)，得到反向的圖G'，對G'上的B做最短路，得出的 cost(B, Y) 既代表反向圖G'上從B到Y的最短路，也代表原圖G上從Y到B的最短路 (此結果的正確性不在此證明，可以自己想想or查網路)