dijkstra堆優(yōu)化及set用法(文件)
【正文】 next。 //初始化為正無窮 path[st] = 0。 if ( st == end ) return path[st]。 p。 //必須先刪除再修改 path的值 ,否則比較關(guān)系就亂了 path[p v] = path[st] + p w。 ( a,b )連到 ( c,b1) 一條邊 ,權(quán)值為 0 ( a,b )連到 ( c,b )一條邊 ,權(quán)值為 k 如果 b=0,則第一條邊就不連了 . 如果 c是空地 ,則連 ( a,b )到 ( c,b )一條權(quán)為 0的邊 . poj3346 Treasure of the Chimp Island ? 技巧 2:由于可以從很多門進入 ,所以我們添加一個虛擬點 ( s, 0 ),把它和所有的門連一條權(quán)值為 0的邊 ? 這樣對新建的圖求最短路就可以得到 ? 這個題目用到了 2個很常用的技巧 ,一個是添加一維變量 ,一個是添加一個虛擬節(jié)點 . 練習(xí)題目 ? toj2217 Invitation Cards ? buaa 1177 Full Tank? ? toj2894 Meetings ? 第一題典型最短路 ,需要求所有點到源點的最短路 ? 第二題和 poj3346很相似 ,需要添加一維變量 ? 第三題是經(jīng)典的貪心算法 ,用 multiset來優(yōu)化 。 } } } return 1。amp。 vis[st] = true。 ( st )。 } Dijkstra算法的優(yōu)化 int dijkstra( int st, int end, int n ) //最短路存在返回路長度 ,否則返回 1 { memset( vis, 0, n )。 //創(chuàng)建 set inline node* creat( int v, int w, node* next ) //申請節(jié)點 { pp v = v。amp。 //記錄最短路 bool vis[MAX]。 struct nn *next。s Idol II ? 題目描述： nuanran有一些圖片，他會收集到新的圖片，但是也會有朋友找他要圖片，所以 nuanran想把當時價值最小的圖片給他的朋友，請你幫助他 ? 輸入：多組數(shù)據(jù)，每組數(shù)據(jù)第一行是整數(shù)n(1 ≤ n ≤
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1