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


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

學校 : 臺北市立內湖高級中學
編號 : 138785
來源 : [118.167.202.23]
最後登入時間 ：
2024-11-29 20:43:48
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)

學校 : 基隆市私立二信高級中學
編號 : 49436
來源 : [114.24.22.164]
最後登入時間 ：
2025-10-08 12:16:07
l747. 連線 -- 三國迷李牧粉題集
| From: [36.227.126.27] | 發表日期: 2025-08-11 16:28

讚！

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

ZeroJudge Forum