UVa 820 Network Bandwidth

題意：
    求S到T的最大流量為多少。網路是雙向連接的，但共用頻寬，例如A B 10，則A到B的流量+B到A的流量要小於等於10。另外這題給測資的方式會有可能給你很多組A B Xi，所以A到B的頻寬要把Xi全部加起來，例如底下例子1~2的頻寬為30。
2
1 2 2
1 2 10
1 2 20
想法：
    Maximum Flow模板題。

POJ 2240 Arbitrage

題意：
    所謂"套匯"指的是透過不斷兌換成別的貨幣，最後再換成原本的貨幣會比本來的錢多。
想法：
    用R[i][j]表示i換成j的匯率，且初始化R[i][i]=1，做Floyd演算法後，去判斷R[i][i]是否大於1，如果大於1表示可以套匯。

POJ 2253 Frogger

題意：
    有隻青蛙要從位置1跳到位置2，假設某路徑途中單次最大跳躍距離為D，求出D的最小値。
    已sample input舉例，如果直接從(17,2)跳到(19,4)，D値為2，但如果從(17,4)跳到(18,5)再跳到(19,4)，D値為1.414。
3
17 4
19 4
18 5

POJ 1860 Currency Exchange

題意：
    假設有A，B兩種貨幣，要將A換成B，須透過匯率Rab和手續費Cab，因此實際得到B貨幣=(A-Cab)*Rab元。  
    第一行輸入N, M, S, V，N表示共有N種貨幣(1<=N<=100)，M表示底下有M行，每一行有六個數字A,B,Rab,Cab,Rba,Cab，Rab表示A換成B的匯率，Cab表示A換成B需要扣除的手續費，Rba和Cba同理。現在Nick有第S種貨幣V元，題目問Nick透過不斷交換貨幣，然後最後換回第S種貨幣的時候能否大於V元?

想法：
    用SPFA演算法，初始除了Dis[S]=V以外Dis[i]都是0，然後不斷更新Dis的值使其盡可能大，最後判斷Dis[S]是否大於V。

POJ 1125 Stockbroker Grapevine

題意：
    N表示共N個點，然後底下N行，第i行第一個數字t表示後面有t個pair，每個pair兩個數字分別代表x, w，i點到x點距離w，注意這是單向道路。題目求從哪個點當作起點可以使得該點走到距離該點最遠的距離為最短。假設i點作起點，走到距離i點最遠的那個點距離為Di，求所有Di中最小的那個值，輸出i及Di。另外題目要求這個i點需要能夠到達所有其他的點。
想法：
    先做Floyd演算法，再去找每個點i的Di，在從Di中選出最小的那個去輸出i及Di即可，注意要判斷這個i是否能到達所有除了i以外的點。

POJ 1724 ROADS

題目：
    總共N個點，給定R條道路，每條共有S,D,L,T代表S點到D點這條路長度L且須花費T元，題目求從1為起點，N為終點，在花費<=K元的情況下走到終點的最短距離。
    注意同一個S到D可能有多條道路。
想法：
    用Dis[i][j]表示"從起點1走到i點花費j元的最短距離"，所以做SPFA的時候，每次就去更新Dis[i][0~K]的值，使其值盡可能的小，最後再去檢查Dis[N][0~K]的最小值是多少。
    因為S到D可能有多條道路，所以用vector來存較為簡單。

UVa 10986 Sending email

這題就是簡單的Shortest path問題，用SPFA即可解決。

UVa 10801 Lift Hopping

題意：
    有n個電梯(1<=n<=5)，每個電梯移動一層樓的時間不一樣，第i個電梯每層樓的移動時間以T[i]表示，而每個電梯能到達的樓層也不一樣，如果兩個電梯都能到達x樓，則能在x樓換另一台電梯搭乘，但轉換的時間為60秒。今天起點在第0樓，給定第k樓為要前往的樓層，問最短的時間?
想法：
    先以Weight[i][j]表示在'不轉換'電梯的情況下，i樓到j樓所需的最短時間，這個部份可以在輸入測資的過程中一起完成。然後再考慮轉換電梯的情況，以Dis[i]表示到達i樓的時間，用SPFA演算法，每次queue的時候就判斷 if (Dis[now] + Weight[now][nxt] + 60 < Dis[nxt]) 來不斷更新Dis[nxt]的值。

UVa 10557 XYZZY

題意：
    總共有N個節點(1~N)，一開始起點在1且有100的能量，踏到每個節點都會有不同的能量變化(-100~+100)，目標是要走到終點N且過程中能量不能歸0。
想法：
    用SPFA演算法，不過要注意過程中可能會碰到正環或是負環，且有正環也不一定能走到終點，因為題目給的是單向的所以有可能走到正環的路走不到終點。因此可以假設如果走了100萬次(數字不一定)還是走不到終點就判定為無法到達。

UVa 10278 Fire Station

題意：
    有F個消防站分布在I個路口，假設每個路口i到離該路口最近的消防站距離為di，而D為這些di的最大值。今天要再增加'一個'消防站在某個路口，求要設在哪個路口使得D為最小。
想法：

1. 先用Floyd演算法求出All pair shortest path
2. 然後求各個路口i到離該路口最近的消防站的距離，用shortest_lenght[i]來存，並找出D值。
3. 從1開始枚舉到I，找出能使得D值最小的路口的編號。