dijkstra堆優(yōu)化及set用法-閱讀頁
2024-10-19 21:43本頁面
【正文】 zeof( path[0] ) )。 ()。 while ( !() ) { st = *()。 ( st )。 Dijkstra算法的優(yōu)化 for ( node* p = adj[st]。 p = p next ) { if ( !vis[p v] amp。 path[p v] path[st] + p w ) { ( p v )。 ( p v )。 } poj3377Ferry Lanes ? 題目概要：一個圖有 200萬個點(diǎn)，每個點(diǎn)最多 3條邊，給定起點(diǎn)終點(diǎn)，求最短路． ? 標(biāo)準(zhǔn)算法：圖是一個特殊的圖（大家有興趣可以看看原題的題目描述）所以可以用O(n)的動態(tài)規(guī)劃解決（參看北大月賽的解題報告 )． ? 我的算法：直接用優(yōu)化的 Dijkstra來計算，復(fù)雜度， n = 600萬， nlogn = 1億 ３ 千萬， 但是實(shí)際上遠(yuǎn)遠(yuǎn)達(dá)不到，可以 AC，由此可見它的速度 poj3346 Treasure of the Chimp Island ? 題目大意 :有一個迷宮 ,里面有寶藏 ,迷宮中有些墻不可以毀掉 ,有些可以毀掉 ,對于可以毀掉的墻 ,你可以花一定時間毀掉 ,或者用炸彈直接炸掉 , 迷宮有一些入口 ,每個入口都有一定量的炸彈 ,你可以從任意一個入口進(jìn)入迷宮 ,但是你一旦從一個門進(jìn)入了 ,就不能走其它的門了 ,在迷宮中行走或者用炸彈炸掉墻都不計算時間 ,只有自己打通墻需要時間 ,問到達(dá)寶藏的地方需要多少時間 ,如果到達(dá)不了就輸出” IMPOSSIBLE”. poj3346 Treasure of the Chimp Island ? 每個門炸彈的數(shù)量為 0到 26,每個可毀掉的墻 ,毀掉它花費(fèi)的時間是 1到 9(如果用炸彈就不需要時間 ) ? 分析 :這是一個比較典型的最短路問題 ,需要 2個比較典型的小技巧 ? 技巧 1:由于花費(fèi)的時間和攜帶的炸彈數(shù)量有關(guān)系 ,所有我們可以構(gòu)建一個新圖 ,一個 2維的圖 ,每個點(diǎn)用 ( a, b )表示 ,a表示迷宮中的點(diǎn) ,b表示攜帶的炸彈的數(shù)量 . poj3346 Treasure of the Chimp Island 點(diǎn) a旁邊的點(diǎn)是點(diǎn) c,而 c是可毀掉的墻 ,花費(fèi)時間 k: 對于 26=
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1