UVa 10048 Audiophobia

題意：
    點與點之間的weight代表聲音的分貝大小，要找一條路徑所遇到的分貝最小，假設a到d某條路徑所遇到的最大分貝為100，另一條路徑所遇到的最大分貝為80，則後者那條路徑較佳。

想法：
    用Floyd演算法找All Pair Shortest Path。

UVa 10000 Longest Paths

    這題是找最長的路徑，我們可以用BellmanFord演算法，與找最短路徑相同的寫法，差別在於我們可以把點到點之間的路徑長變"負"的，最後找負最多的那個點就是最遠的點。

UVa 341 Non-Stop Travel

題意：
    Ruby兔中文翻譯
想法：
    用BellmanFord演算法找出最短路徑，並在找的過程中用Pre[i]紀錄什麼點走到i，最後在從終點利用Pre走回起點，並依題目輸出答案。

POJ 3259 Wormholes

題意：
    FJ要找出是否能從某個起點出發，然後回到該起點但可以遇見出發時的自己，也就是時間和要<0。

• 題目N表示有幾個點
• M表示有M行，每行S,E,T三個數字表示S點到E點或E點到S點所需要的時間是T
• W表示有W行，每行S,E,T三個數字表示S點到E點所減少的時間T，也就是S到E你的時間總和會-T，注意這個是單向的，只有S點到E點

想法：

    本題換句話說就是找出是否有負環(negative cycle)，確認在所有路徑中是否存在一個cycle，使得一直走那個cycle時間總合會越來越小。

POJ 2387 Til the Cows Come Home

這題其實就是要求終點走到起點的最短路徑，因此用個簡單的BellmanFord演算法即可解決這題。

UVa 10534 Wavio Sequence

Longest Increased/Decreased Subsequence
想法：
    替數列建LIS和LDS表，然後在從表中找出共同最大的數字。例如：
數列： 1 2 3 4 5 3 2
LIS：  0 1 2 3 4 0 0
LDS：  0 0 0 0 2 1 0
因此數字'5'的LIS為4,LDS為2，所以'5'為中心組成Wavio Sequence的長度就是min(4,2)*2+1=5。因此本題就從LIS和LDS表中找出最長的Wavio Seq長度。
    至於求LDS我是由後面往前作LIS，因此這題就是做兩次LIS，另外要注意如果用O(n^2)演算法可能會TLE。

UVa 437 The Tower of Babylon

題目：
    LuckyCat中文翻譯
想法：
    Longest Increased Subsequence題型，每種Block都有6種組合，所以每次讀入一組L,W,H，就存6種組合，等到全部讀完，就將全部的組合進行排序。因為我是打算將Block由小疊到大(做LIS，與題目相反)，所以排序方式就依L由小到大排，如果L一樣在依W排，然後就做LIS演算法。

UVa 836 Largest Submatrix

想法：
    這題是2維MSS(minimum subarray sum)，基本上第一個for loop先選出submatrix的垂直邊長，第二個for loop選定這條邊起始位置，然後向右做MMS。

UVa 507 Jill Rides Again

Minimum Subarray Sum
想法：
    這題求最大MSS值的區間，注意output說明，如果MSS一樣的話，要選擇最大的區間長度(j-i盡可能大)，如果區間長度又一樣長的話，那麼要選擇先出現的那個。

• 區間長度盡可能大：第18行要用">="
• 選擇最大區間長度：第24行的判斷式

UVa 231 Testing the CATCHER

Longest Decreased Subsequence
題意：
    Ruby兔中文翻譯
想法：
    由後往前用LIS。