難度: 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