dijkstra堆優(yōu)化及set用法(參考版)
2024-10-03 21:43本頁面
【正文】 ( 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:由于可以從很多門進(jìn)入 ,所以我們添加一個(gè)虛擬點(diǎn) ( s, 0 ),把它和所有的門連一條權(quán)值為 0的邊 ? 這樣對(duì)新建的圖求最短路就可以得到 ? 這個(gè)題目用到了 2個(gè)很常用的技巧 ,一個(gè)是添加一維變量 ,一個(gè)是添加一個(gè)虛擬節(jié)點(diǎn) . 練習(xí)題目 ? toj2217 Invitation Cards ? buaa 1177 Full Tank? ? toj2894 Meetings ? 第一題典型最短路 ,需要求所有點(diǎn)到源點(diǎn)的最短路 ? 第二題和 poj3346很相似 ,需要添加一維變量 ? 第三題是經(jīng)典的貪心算法 ,用 multiset來優(yōu)化 。 } } } return 1。 //必須先刪除再修改 path的值 ,否則比較關(guān)系就亂了 path[p v] = path[st] + p w。amp。 p。 vis[st] = true。 if ( st == end ) return path[st]。 ( st )。 //初始化為正無窮 path[st] = 0。 } Dijkstra算法的優(yōu)化 int dijkstra( int st, int end, int n ) //最短路存在返回路長(zhǎng)度 ,否則返回 1 { memset( vis, 0, n )。 pp next = next。 //創(chuàng)建 set inline node* creat( int v, int w, node* next ) //申請(qǐng)節(jié)點(diǎn) { pp v = v。 } }。amp。a, const int amp。 //記錄最短路 bool vis[MAX]。 Dijkstra算法的優(yōu)化 node pool[MAX], *pp, *adj[MAX]。 struct nn *next。s Idol II ? 樣例輸出： 10 9 20
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1