發表新討論
#41950: Floyd Warshall 裸題


s10900156@nhsh.tp.edu.tw (ShanC)

學校 : 臺北市立內湖高級中學
編號 : 138785
來源 : [118.167.222.118]
最後登入時間 ：
2024-05-23 14:23:16
l747. 連線 -- 三國迷李牧粉題集 | From: [118.167.220.35] | 發表日期 : 2024-09-13 08:25

由於節點數很少 因此可以考慮 Floyd Warshall

我做的步驟如下: 

  1. 沒出現的節點給一個編號
  2. 將輸入的兩節點 s, t 邊權設成 1 存入 dis[s][t](記得因為是無向邊 所以 dis[t][s] 也要)
  3. 跑 Floyd Warshall
  4. 如果被詢問的邊 s-t 有被窮舉到 那 dis[s][t] 應該不會是INF 由此依據去判斷答案
 
ZeroJudge Forum