算法合集之《淺談最短徑路問題中的分層思想》-文庫吧
2025-09-19 18:37 本頁面
【正文】 匙。 把每個單元看成頂點，相互連通的單元之間連一條邊權(quán)為 1的邊。 分析 — 分層 考慮鑰匙狀態(tài)對門的影響。 把圖分成 2P層，分別對應(yīng)持有鑰匙的 2P種狀態(tài)。 分析 — 邊（ 1） 根據(jù)鑰匙的狀態(tài)改造每層圖 ， 使相鄰的連通節(jié)點間有長度為 1的邊。 分析 — 邊（ 2） 對于存有鑰匙的頂點，向表示得到鑰匙后鑰匙狀態(tài)的層的對應(yīng)頂點連一條長度為0的邊。 分析 — 復(fù)雜度 使用寬度優(yōu)先搜索求最短路。 時間復(fù)雜度和空間復(fù)雜度均為O(2PNM)。 小結(jié) 將圖進行分層是因為在同一層圖上難以準(zhǔn)確地表現(xiàn)出圖在不同條件下的狀況或圖的其他因素。 分層的圖分別表示不同的條件，加強了圖的性質(zhì)，使得在分層圖能夠使用基本的最短路算法求解原來的復(fù)雜問題。 例題二 roads (CEOI98) n個城市有單向道路連接。 每條路有固定的長度和費用。 路徑上的費用不大于 k。 求從城市 1出發(fā)到達城市 n的最短路徑。 例題二 roads (CEOI98) 費用 k是不大于 10000的非負整
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1