第一題 hdu 1317 XYZZY
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1317">點選打開hdu 1317</a>
思路：
1 題目的圖是一個有向圖，并且可能存在環。第一個點的能量值為100，邊的權值利用能量大小，例如2點為-60，如果1->2那麼value[1][2] = -60
2 題目明确指出如果是要win的話，那麼必須是經過的每條邊都要大于0.那麼我們隻要把那些經過松弛操作後的點大于0的入隊即可，小于等于0的點肯定不會出現在最終的路徑上。
3 如果存在正環的話，那麼就有能量值無限大，那麼這個時候隻要判斷這個點能否到達n
4 判斷是否是有環還是五環，用一個s标記，s初始化為0，有環的時候另s = i，然後return。
5 判斷目前點s能否到n直接利用dfs即可。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/7734776">點選檢視代碼</a>
第二題 uva 567 Risk
<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=508&mosmsg=Submission+received+with+ID+10622709">點選打開uva 567</a>
思路：最短路的模闆題
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/7996412">點選檢視代碼</a>
第三題 hdu 1874 暢通工程續
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1874">點選打開hdu 1874</a>
思路：最短路模闆題
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/7997820">點選檢視代碼</a>
第四題 uva 558 Wormholes
<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=499&mosmsg=Submission+received+with+ID+10628131">點選打開uva 558</a>
1 利用Bellman_Ford來判斷是否存在回環
2 在利用Bellman_Fordde 時候如果做了n-1次的松弛步以後還能更新dis數組，那麼說明原來的圖中存在環，那麼最短路就是不存在的。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8002074">點選檢視代碼</a>
第五題uva 10986 Sending email
<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=1927&mosmsg=Submission+received+with+ID+10629266">點選打開uva 10986</a>
1 題目給定的n最大20000，m最大50000，分析複雜度後發現隻有SPFA最靠譜。
2 分析題目的樣列可知，這一題是要用鄰接矩陣來存儲無向圖，是以要注意無向圖怎麼存儲在鄰階表中
2 連接配接表的橫列有N項，縱列也是N項。形成的N*N項每項都被稱為邊結點，每項都有縱橫兩個坐标，例如點（N,N-1），表示的就是從第N點向第N-1點有無路徑。由于有E條邊，自然有E條路徑，但是由于無向=雙向，是以要乘以2。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8002481">點選檢視代碼</a>
第六題 uva 10801 Lift Hopping
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8007698">點選打開uva 10801</a>
1 有n個電梯，電梯可以到達的層數是一定的，那麼我們就把樓層看成是圖上的點，那麼我們就可以得到的哪些點是有連通的。
2 又由于有多個電梯，是以x->y可能有多種方式，是以這就類似于重邊問題那麼我們要選擇邊權值最小的最為最後的邊權值。
3 接下來圖建好以後就是考慮怎麼Dijkstra，由于要交換乘坐電梯，那麼我們就自然的想到了圖論中的換邊（松弛步），那麼我們就把換乘電梯看成是在換邊，就是說隻要做松弛步就是在換成電梯，那麼這個時候就要加上等電梯的時間60s。
4 這裡有個地方就是由于源點是會做松弛步的，但是源點是不用加上60s的，是以最後輸出的時候要特判一下。如果k為0，直接輸出0；如果k部位0，那麼最後的輸出要減去60。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8007698">點選檢視代碼</a>
第七題 hdu 2544 最短路
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=2544">點選打開hdu2544</a>
思路：模闆題
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8008081">點選檢視代碼</a>
第八題 hdu 3790 最短路徑問題
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3790">點選打開hdu 3790</a>
由于題目要求在最短路徑的時候花費最少，那麼這就是在做松弛操作的時候判斷一下目前的選擇的邊的花費是不是最少的，那麼這樣就可以求出最少的花費。利用最短路的思想即可
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8014034">點選檢視代碼</a>
第九題 hdu 1548 A strange lift
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1548">點選打開hdu 1548</a>
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8045122">點選檢視代碼</a>
第十題 hdu 2066 一個人的旅行
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=2066">點選打開hdu2066</a>
題目給定的起點有s個，終點有d個。要求找到從起點到這些終點最短的路徑。很顯然隻要枚舉起點然後比較最後得到最小的值。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8045301">點選檢視代碼</a>
第十一題 hdu 2112 HDU Today
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=2112">點選打開hdu 2112</a>
1 題目中的起點和終點可能相同，這個時候輸出0。
2 用map映射的時候用char類型，由于string是個類效率比較低。
3 處理成無向圖
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8046624">點選檢視代碼</a>
第十二題 hdu 1217 Arbitrage
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1217">點選打開hdu 1217</a>
1 題目要求的是經過一輪的轉換之後，原來的比例能夠大于1。比如原先的“美元：美元 = 1：1”,最後要求能夠達到“美元：美元 > 1”
2 假設dis[i][j]表示“i ： j”的比例，那麼初始化dis[i][i] = - 1。
3 由于n最大為30，是以果斷選擇floyd算法。但是這裡有個地方不同的是，這裡并不是要求最小而是求最大，是以應該要把“小于改成大于”
4 最後隻要能夠找到一種貨币的兌換比例大于1即滿足條件
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8056444">點選檢視代碼</a>
第十三題 hdu 1245 Saving James Bond
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1245">點選打開hdu 1245</a>
1 題目講的是有一個湖100x100這個人剛開始在一個直徑為15的圓心在原點的園内，然後要通過跳躍的方式問我們他是否能夠到達岸邊。如果可以求出最短的路徑和步數
2 很明确就是最短路問題。但是這個時候問題來了，起點和終點是在哪裡，是以我們采用的是将原點作為起點，岸邊做為終點。知道了起點和終點，我們就可以求最短路，但是這個時候會碰到另外一個問題，邊的長度。對于這個問題，我們是采取的方法是将這些點分成三類。1類：起點 2類：終點 3類：其它點 ，那麼我們就可以分别對這三類的點求出它和其它點的距離。
注意事項：
1 輸入的資料中，點的範圍可能會在園内或在湖外，是以在輸入的時候要判斷點是否合法。
2 這一題精度要求很嚴格，一些比較之類的要注意精度問題
3 注意n = 0 的情況，這裡如果n = 0，但是d > 42.5 是可以跳出去的。但是隻要有烏龜，這個人就必須通過踩在烏龜上面跳出去，是以n = 0是比較特殊的。
4 n不大是以什麼方法都可以做
5 求所需幾步的時候利用一個setp[][]數組，首先初始戶為0然後将可以到達的點标記為1，最後隻要在更新dis[][]的時候更新即可。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8059793">點選檢視代碼</a>
第十四題 hdu 1535 Invitation Cards
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1535">點選打開連結</a>
1 題目要求的是總的最小的花費，意思就是要求每一個人的花費都最小。
2 由于每一個人都是從1出去，最後還是都要回到1的，那麼求解的時候就要分成兩部分“出去+回來”；出去的話直接利用SPFA(1)，1作為起點即可求出每一點的最小花費，回來的話如果是直接利用對每一個人進行SPFA，那麼這樣肯定逾時。仔細想想要求的是每一個點到1的最小距離，那麼由于給定的是一個有向圖，那麼隻要重建立圖把邊反向，那麼我們所求的問題就變成1到每一個點的最小距離。是以隻要兩步SPFA(1)即可。
3 資料類型為long long
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8067131">點選檢視代碼</a>
第十五題 hdu 1546 Idiomatic Phrases Game
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1546">點選打開hdu 1546</a>
1 隻要建好圖，然後利用SPFA求解最短路即可。注意字元串的處理
2 定義一個char ch[10]數組，如果給數組的每一個元素值指派後，還要記得要在最後ch[9]添加‘\0’，表示結束。就是如果要儲存10個元素，那麼數組最小要開到11，因為第11個表示‘\0’來表示正常結束。是以數組盡量開大點
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8067460">點選檢視代碼</a>
第十六題 hdu 2680 Choose the best route
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=2680">點選打開hdu 2680</a>
1 題目要求的是從某一個站點能否到達目标站點
2 題目的其實站點有多個，如果都對每一個站點進行SPFA的話那麼肯定TLE的。是以這個時候我們想到了增加一個新的點0，用來作為新的起點。這個時候隻要把能夠和0相連的點的權值标記為0即可。
3 注意這一題的圖是一個有向圖
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8068213">點選檢視代碼</a>
第十七題 hdu 2923 Einbahnstrasse
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=2923">點選打開hdu 2923</a>
1 題目要求的是有n個點，然後有c個破車，這個c個破車可能在同一城市裡面，現在要把這些破車統一拉到中心點1.
2 這題的中心在1點，那麼所求 ans = 1->所有破車的距離之和 + 所有破車->1的之和。是以這裡涉及到1->所有破車的距離 和 所有破車->1的距離，那麼我們可以使用SPFA和floyd。如果使用的是floyd那麼最後的ans = dis[1][i]+dis[i][1]；如果是SPFA就要先求一下1->所有破車的距離之和，然後在重建立圖就是把邊反向然後對1點SPFA ，在加上1->所有破車的和即可。
4 點的表示，利用map映射。
3 這一題給的n雖然才100，但是利用SPFA的時候要數組記得開1010，因為c最大為1000.這個地方杭電是WA，不給RE，是以我WA了40+。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8071207">點選檢視代碼</a>
第十八題 hdu 3339 In Action
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3339">點選打開hdu 3339</a>
1 這一題多了一個限制條件能量，即每一點都有一個自己的能量值。
2 問題是要求能量至少要大于1/2的情況下的最短路，最開始我了解成是貪心，然後就是無休止的的WA，後來才知道是dp。其實很好了解，對于每一個點的能量隻有兩種選擇取或者不取，那麼這就是典型的0/1背包問題。但是有一個問題就是選取什麼作為背包的容量，剛開始我選擇pow_sum作為背包的容量，然後距離為價值求dp，然後又是一頓WA。後來改成了以cost_sum作為背包的容量，然後pow作為價值求解dp，最後判斷是否有一個
dp[i] > sum/2然後就1 A了。
3 注意題目明确指出有多個坦克，意思就是每一個坦克都從0開出并且隻能攻擊一個點。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8074450">點選檢視代碼</a>
第十九題 hdu 2807 The Shortest Path
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=2807">點選打開hdu 2807</a>
1 題目明确要求x->y是否有了，而且有多次詢問，是以序則floyd
2 題目給的點的形式是矩陣，是以還要去處理矩陣，判斷A*B=C
3 題目說了A B C三個城市，是以做A B C三個是不同的
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8074966">點選檢視代碼</a>
第二十題 hdu 1595 find the longest of the shortest
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1595">點選打開hdu 1595</a>
1 題目要求的是删掉一條邊之和求出的最短路中的最大值。
2 很明顯，肯定是要先求出原圖的最短路并且記錄父親節點。現在我們可以想，如果要枚舉所有的邊，顯然這個是不可能的實作的。是以我們仔細分析可以知道其實能夠對最短路産生影響的就是原圖最短路上的邊，是以我們隻需要去枚舉删除最短路徑上面邊然後求最短路即可，最後得到ans
3 這一題的n <= 1000 , m<=n*(n-1)/2 , 剛開始我用的SPFA，然後就開始TLE。後來知道了，有些時候SPFA的期望值中O(ke)，有些題目會卡k，是以這個時候隻能選擇優先隊列的Dij算法了。
4 題目用到了捆綁兩種類型的pair<int , int>pii;
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8076415">點選檢視代碼</a>
第二十一題 hdu 1599 find the mincost route
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1599">點選打開hdu 1599</a>
1 題目要求的是能否有從某一個點出發至少經過兩個不同點然後回到源點，有的話求最小路徑長度。
2 題意很明确就是要求最小環問題 ， 是以現在用到了floyd的一個擴充求解圖上最小環。
3 <<floyd求解環中的最小環>>
1 為什麼要在更新最短路之前求最小環：
在第k層循環，我們要找的是最大結點為k的環，而此時Dist數組存放的是k-1層循環結束時的經過k-1結點的最短路徑，也就是說以上求出的最短路是不經過k點的，這就剛好符合我們的要求。為什麼呢？假設環中結點i,j是與k直接相連，如果先求出經過k的最短路，那麼會有這樣一種情況，即：i到j的最短路經過k。這樣的話就形成不了環 。
2最小環改進算法的證明：
一個環中的最大結點為k(編号最大)，與他相連的兩個點為i,j，這個環的最短長度為g[i][k]+g[k][j]+dis[i][j] (i到j的路徑中,所有結點編号都小于k的最短路徑長度)。根據floyd的原理，在最外層循環做了k-1次之後，dist[i][j]則代表了i到j的路徑中，所有結點編号都小于k的最短路徑, 綜上所述，該算法一定能找到圖中最小環。
3 為什麼還要value數組：
因為dis數組時刻都在變動不能表示出原來兩個點之間的距離。
4 形成環至少要有3點不同的點，兩個點是不能算環的，是以有i , j , k不同。
4 注意：hdu有時候比較特别，你使用long long的話oj給的是WA，這一題我用long long WA了，是以用int。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8079478">點選檢視代碼</a>
第二十二題 hdu 3986 Harry Potter and the Final Battle
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3986">點選打開hdu 3986</a>
1 題目要求的是删除一條之和的最壞情況，并不是删除一條邊之後的最短路（WA了好久不解釋）。如果都可以到n，那麼輸入删除一條之後的最短路徑。
2 利用鄰階表+優先隊列優化+Dij可以做
3 father數組記錄的是在原圖中的1->n的最短路徑中目前這個點的前一條邊的編号。
4 在鄰階表裡删除一條邊相當于就是邊的權值變為INF
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8082949">點選檢視代碼</a>
第二十三題 hdu 1839 Delay Constrained Maximum Capacity Path
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1839">點選打開hdu 1839</a>
1 題目要求的是在限制時間t之内，最大的容量。而題目說了最大的容量就是路徑上的最小的邊值。
2 這裡加了一個容量，而且是要求一條邊的最短。是以這裡用到了二分，因為我們知道随着邊長的增大能夠滿足的路徑越來越少，是以我們隻要去枚舉容量即可。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8087906">點選檢視代碼</a>
第二十四題 hdu 3631 Shortest Path
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3631">點選打開hdu 3631</a>
1 題目給的n <= 300，而邊數m<=100000，并且有Q<= 100000次詢問。剛開始我用優先隊列+Dij然後就開始TLE，然後就沒然後了。
2 看了題解之後猛然發現這尼瑪就是floyd,（對算法了解不透測）。我們知道floyd就是每次都拿一個中間點k來更新dis，題目中是隻有标記過的點才能夠使用，那麼就像floyd一樣隻要是标記來這個點那麼就可以用這個點來進行更新dis，然後如果要求兩點直間的距離隻要查找即可。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8090859">點選檢視代碼</a>
第二十五題 hdu 1869 六度分離
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1869">點選打開hdu 1869</a>
1 題目是要求所有的資料能否滿足“六度分離”，那麼我們就想到所有點之間的最短距離。
2 應用floyd，如果兩點之間有聯系那麼距離标記為1，那麼最後隻要判斷是不是每兩個人之間的距離是不是都不大于7（這裡為什麼是7不是6自己畫圖）.
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8091674">點選檢視代碼</a>
第二十六題 hdu 1224 Free DIY Tour
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1224">點選打開hdu 11224</a>
1 提要要求的最大的環，蛋并不是這麼的複雜，因為第一個點的points值為0，是以其實就是求1到某一個點的最長路，其實就是最長路問題
2 注意的是在求1到某一個點的最長路的時候還要注意這個點是否能夠到達1點，這個可以用一個mark數組來标記
3 可以更簡單的做法就是1-n+1的最長路。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8093639">點選檢視代碼</a>
第二十七題 hdu 1385 Minimum Transport Cost
<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=1385">點選打開hdu 1385</a>
1 題目要求的單源的最短路，是以可以選擇任意一種單源最短路來求解
2 題目還要求在路徑和相同情況下要字典序小的，那麼就要在更新dis數組的時候進行更新路徑，如果是dis[i]>tmp,那麼直接更新；如果是dis[i] == tmp的情況下，那麼就要求出star->i 和 star->x的路徑進行比較，然後判斷能否更新.
3 注意詢問的時候可能問的是同一個點。
<a target="_blank" href="http://blog.csdn.net/chenguolinblog/article/details/8094659">點選檢視代碼</a>
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)