dijkstra堆優(yōu)化及set用法-資料下載頁
2024-09-29 21:43本頁面
【導讀】Set，顧名思義，就是集合的意思。它支持插入，刪除，查找，首元素，末元素。而且所有的操作都是在嚴格logn時間之內完。Set是一個有序的容器，里面的元素都是排好。Set的實現(xiàn)是通過２叉排序樹來實現(xiàn)，就是將。這樣樹就有可能退化成一條線，所以Set用一。比較關系是有要求的，必須和實數(shù)的＜類。１．如果a<b,b<c則有a<c，即比較關。２．a<b和b<c不能同時成立。{定義類型}ss(類型名);以base為例說明Set的操作。尾，返回迭代器，這個迭代器里沒有元素，須在容器中放入相同的元素就要使用multiset，Set和multiset都是引用<set>頭文件,復雜度都是。對于內置的數(shù)據(jù)類型，如int,double等是不能重載<的，nuanran有一些圖片，他會收集到新的圖片，分析，這道題的實質就是維護一個集合，multiset來實現(xiàn)，代碼會很輕松的實現(xiàn)！其中第2步中找到最小的path值的點可以用set來實
【正文】 Treasure of the Chimp Island ? 題目大意 :有一個迷宮 ,里面有寶藏 ,迷宮中有些墻不可以毀掉 ,有些可以毀掉 ,對于可以毀掉的墻 ,你可以花一定時間毀掉 ,或者用炸彈直接炸掉 , 迷宮有一些入口 ,每個入口都有一定量的炸彈 ,你可以從任意一個入口進入迷宮 ,但是你一旦從一個門進入了 ,就不能走其它的門了 ,在迷宮中行走或者用炸彈炸掉墻都不計算時間 ,只有自己打通墻需要時間 ,問到達寶藏的地方需要多少時間 ,如果到達不了就輸出” IMPOSSIBLE”. poj3346 Treasure of the Chimp Island ? 每個門炸彈的數(shù)量為 0到 26,每個可毀掉的墻 ,毀掉它花費的時間是 1到 9(如果用炸彈就不需要時間 ) ? 分析 :這是一個比較典型的最短路問題 ,需要 2個比較典型的小技巧 ? 技巧 1:由于花費的時間和攜帶的炸彈數(shù)量有關系 ,所有我們可以構建一個新圖 ,一個 2維的圖 ,每個點用 ( a, b )表示 ,a表示迷宮中的點 ,b表示攜帶的炸彈的數(shù)量 . poj3346 Treasure of the Chimp Island 點 a旁邊的點是點 c,而 c是可毀掉的墻 ,花費時間 k: 對于 26=b0。 ( a,b )連到 ( c,b1) 一條邊 ,權值為 0 ( a,b )連到 ( c,b )一條邊 ,權值為 k 如果 b=0,則第一條邊就不連了 . 如果 c是空地 ,則連 ( a,b )到 ( c,b )一條權為 0的邊 . poj3346 Treasure of the Chimp Island ? 技巧 2:由于可以從很多門進入 ,所以我們添加一個虛擬點 ( s, 0 ),把它和所有的門連一條權值為 0的邊 ? 這樣對新建的圖求最短路就可以得到 ? 這個題目用到了 2個很常用的技巧 ,一個是添加一維變量 ,一個是添加一個虛擬節(jié)點 . 練習題目 ? toj2217 Invitation Cards ? buaa 1177 Full Tank? ? toj2894 Meetings ? 第一題典型最短路 ,需要求所有點到源點的最短路 ? 第二題和 poj3346很相似 ,需要添加一維變量 ? 第三題是經典的貪心算法 ,用 multiset來優(yōu)化
教學課件相關推薦
鄂ICP備17016276號-1