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


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

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 由此依據去判斷答案
#50768: Re: Floyd Warshall 裸題


rsj00008 (西加008)

l747. 連線 -- 三國迷李牧粉題集 | From: [36.227.126.27] | 發表日期: 2025-08-11 16:28

讚！

但要注意最後一列字串l和字串o，有可能在前面t列沒出現過

ZeroJudge Forum