胡桃敲可愛的~

分析、實現(xiàn)

先貼上 dijkstra 求最短路的代碼：

與題中的 dfs 對比，很容易發(fā)現(xiàn)在 dijkstra 算法中，每當一個結(jié)點 ?被進行計算時，它會比較所有的前驅(qū)結(jié)點，最終留下最優(yōu)值。

但在 dfs 算法中，一個結(jié)點最多只會被計算一次。不難發(fā)現(xiàn)，當一個結(jié)點有且僅有一個前驅(qū)時，dfs 算法才能正確計算最短路。

而此時圖實際上是一棵無根樹，這個 dfs 算法實際上是用來計算樹上結(jié)點深度的正解。

所以當且僅當結(jié)點 ?所在連通塊是一棵樹時，才能正確進行最短路計算。否則，一旦結(jié)點 ?所在連通塊中出現(xiàn)環(huán)，環(huán)上部分節(jié)點計算必然出錯。

綜上所述，只需要對結(jié)點 ?所在連通塊檢查是否存在環(huán)即可。

（其實還有一種簡單粗暴的辦法，用 dfs 和 dijkstra 各運行一遍，比較答案。）

Code

胡桃敲可愛的~