a764: pC. Tony 與只有神知道的世界

a764: pC. Tony 與只有神知道的世界

題 意:

求 無 向 圖 最 小 環。

solve:

假 設 最 小 環 上 編 號 最 大 的 點 為 $k$，而 相 鄰 兩 點 為 $i$ 與 $j$，則 最 小 環 路 徑 長 為 $dis(k, i) + dis(i, j) + dis(j, k)$。

用 Floyd-Warshall 枚 舉 $k$ 的 同 時，順 便 求 $i$ 跟 $j$ 的 最 短 路 徑。
(FW 有 一 個 性 質 : 最 外 層 循 環 到 $z$ 時，最 短 路 徑 只 會 經 過 編 號 $[1, z)$ 的 點)

code: