前往
大廳
主題

[leetcode]882. Reachable Nodes In Subdivided Graph

♙♲⚙\~O_O~/⚙♲♙ | 2021-08-04 12:00:11 | 巴幣 2 | 人氣 194

題目: 882. Reachable Nodes In Subdivided Graph
難度: Hard
目前下列解法的時間複雜度: O(n*n) ( O(|E|) , E for edges )


題目說明

以邊給定一張圖G,每個邊上有個數字c,代表這個邊上要生成c個新節點,所以分成c+1段。
稱此生完新節點的圖為H。
問從節點 0 (節點編號從0開始) 開始,每經過一個節點需動 1 步,最多動 m 步,共可以在 H 上經過多少個節點。


解法

如果沒有新增節點,那就只是問距離內的節點有誰, BFS + min_heap 相信不難。
現在有新增節點,就只是再從距離內的節點走完邊上的節點。所以:
1. 用BFS走完原節點取得每個節點的距離
2. 步數範圍內的原節點再去找他延伸出去的邊還可以走幾個節點
3. 記得記下從兩原端點走過幾個節點,以免重複計算


source code

創作回應

相關創作

更多創作