算法合集之淺談最短徑路問題中的分層思想-wenkub
2022-11-02 18:37:45 本頁面
【正文】 費(fèi)用，邊的權(quán)值表示道路長度。 例題二 roads (CEOI98) 費(fèi)用 k是不大于 10000的非負(fù)整數(shù) 城市數(shù) n是不大于 100的正整數(shù) 道路數(shù) m是不大于 10000的正整數(shù) 每條道路的長度是不大于 100的正整數(shù) 每條道路的通行稅是不大于 100的非負(fù)整數(shù)。 例題二 roads (CEOI98) n個(gè)城市有單向道路連接。 分析 — 復(fù)雜度 使用寬度優(yōu)先搜索求最短路。 分析 — 分層 考慮鑰匙狀態(tài)對門的影響。 求從 (1,1)到 (N,M)的最短時(shí)間。 南北或東西方向相鄰的兩個(gè)單元之間可以互通，或者存在一扇鎖著的門，又或者存在一堵不可逾越的墻。 迷宮中有一些單元存放著鑰匙，總共有 P類鑰匙，對應(yīng) P類門。 N,M不大于 15， P不大于 10。 把圖分成 2P層，分別對應(yīng)持有鑰匙的 2P種狀態(tài)。 時(shí)間復(fù)雜度和空間復(fù)雜度均為O(2PNM)。 每條路有固定的長度和費(fèi)用。 分析 — 圖 我們把城市看成節(jié)點(diǎn)，城市之間的道路看成邊。 1 5 4 2 3 6 1 5 4 2 3 6 1 5 4 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1