dijkstra堆優(yōu)化及set用法-文庫吧資料
2024-10-07 21:43本頁面
【正文】 ? 分析，這道題的實質就是維護一個集合，支持 ２ 個操作，插入一個元素，刪除最小元，這個可以用堆來實現(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。s Idol II ? 題目描述： nuanran有一些圖片，他會收集到新的圖片，但是也會有朋友找他要圖片，所以 nuanran想把當時價值最小的圖片給他的朋友，請你幫助他 ? 輸入：多組數(shù)據(jù)，每組數(shù)據(jù)第一行是整數(shù)n(1 ≤ n ≤ 100000)，表示下面有 n行 每行有 ２ 種形式： “ B S” ：表示得到價值為 S的圖片 “ G” ：表示要給出當時價值最小的圖片 n = 0表示輸入結束． toj2196Nuanran39。 setint,cmp base。a, const int amp。 ( a ) 查找元素 a的數(shù)量，返回整數(shù) set和 multiset ? Set要求容器里的元素在定義的比較關系下都是不同的，如果已經(jīng)有，那么 insert是無效的，如果必須在容器中放入相同的元素就要使用 multiset，multiset和 set有幾點不同： ? 創(chuàng)建 multisetss base。 ( 創(chuàng)建一個元素類型是 ss,名字是 base的 set ) ? 注：定義了＜，＝＝和＞以及＞＝，＜＝就都確定了，STL的比較關系都是用＜來確定的，所以必須通過定義＜ －－“嚴格弱小于”來確定比較關系 Set的操作 ? 以 base為例說明 Set的操作 () 清空 base ( a ) 插入元素 a ( a ) 刪除元素 a,如
教學課件相關推薦
鄂ICP備17016276號-1