dijkstra堆優(yōu)化及set用法(編輯修改稿)
2024-11-04 21:43 本頁面
【文章內容簡介】 行有 ２ 種形式： “ B S” ：表示得到價值為 S的圖片 “ G” ：表示要給出當時價值最小的圖片 n = 0表示輸入結束． toj2196Nuanran39。s Idol II ? 輸出：按照“ G”的順序輸出所有給出圖片的價值 開始時 nuanran沒有圖片 ? 樣例輸入： 8 B 20 B 10 G B 9 G B 100 B 25 G 0 toj2196Nuanran39。s Idol II ? 樣例輸出： 10 9 20 ? 分析，這道題的實質就是維護一個集合，支持 ２ 個操作，插入一個元素，刪除最小元，這個可以用堆來實現(xiàn)，不過如果用multiset來實現(xiàn)，代碼會很輕松的實現(xiàn)！大家可以試試 Dijkstra算法的優(yōu)化 ? 復習一下算法： s表示起點， t表示終點， path數(shù)組表示所有點到 s的距離 ,集合 S表示已經(jīng)找到最短路的點集． 1， path[s] = 0, 其他 path為正無窮， S為空集 2，找到不在 S中 path值最小的點，用它更新周圍點的 path值，然后把它加到 S中 3，如果 t不在 S中，重復 2，否則退出 Dijkstra算法的優(yōu)化 ? 其中第 2步中找到最小的 path值的點可以用 set來實現(xiàn) : include include include set define MAX 1000000 using namespace std。 typedef struct nn { int v, w。 struct nn *next。 } node。 Dijkstra算法的優(yōu)化 node pool[MAX], *pp, *adj[MAX]。 //申請節(jié)點前一定要 pp = pool int n, path[MAX]。 //記錄最短路 bool vis[MAX]。 struct cmp { bool operator()( const int amp。a, const int amp。b ) const { return path[a] path[b] || ( path[a] == path[b] amp。amp。 a b )。 } }。 //這里用 p
教學課件相關推薦
鄂ICP備17016276號-1