[編程題]比較重量
小明陪小紅去看鉆石亏吝，他們從一堆鉆石中隨機抽取兩顆并比較她們的重量掠哥。這些鉆石的重量各不相同。在他們們比較了一段時間后腮介，它們看中了兩顆鉆石g1和g2。現(xiàn)在請你根據(jù)之前比較的信息判斷這兩顆鉆石的哪顆更重端衰。
給定兩顆鉆石的編號g1,g2叠洗，編號從1開始，同時給定關系數(shù)組vector,其中元素為一些二元組旅东，第一個元素為一次比較中較重的鉆石的編號灭抑，第二個元素為較輕的鉆石的編號。最后給定之前的比較次數(shù)n抵代。請返回這兩顆鉆石的關系腾节，若g1更重返回1，g2更重返回-1荤牍，無法判斷返回0案腺。輸入數(shù)據(jù)保證合法，不會有矛盾情況出現(xiàn)康吵。
測試樣例：

2,3,[[1,2],[2,4],[1,3],[4,3]],4

返回: 1

只有五行的 Floyd 最短路算法

暑假救湖，小哼準備去一些城市旅游。有些城市之間有公路涎才，有些城市之間則沒有鞋既，如下圖力九。為了節(jié)省經(jīng)費以及方便計劃旅程，小哼希望在出發(fā)之前知道任意兩個城市之前的最短路程邑闺。

上圖中有 4 個城市 8 條公路跌前，公路上的數(shù)字表示這條公路的長短。請注意這些公路是單向的陡舅。我們現(xiàn)在需要求任意兩個城市之間的最短路程抵乓，也就是求任意兩個點之間的最短路徑。這個問題這也被稱為“多源最短路徑”問題靶衍。

現(xiàn)在需要一個數(shù)據(jù)結構來存儲圖的信息灾炭，我們仍然可以用一個 4*4 的矩陣（二維數(shù)組 e）來存儲。比如 1 號城市到 2 號城市的路程為 2颅眶，則設 e[1][2]的值為 2蜈出。2 號城市無法到達 4 號城市，則設置 e[2][4]的值為 ∞涛酗。另外此處約定一個城市自己是到自己的也是 0铡原，例如 e[1][1]為 0，具體如下商叹。

現(xiàn)在回到問題：如何求任意兩點之間最短路徑呢燕刻？通過之前的學習我們知道通過深度或廣度優(yōu)先搜索可以求出兩點之間的最短路徑。所以進行 n2 遍深度或廣度優(yōu)先搜索剖笙，即對每兩個點都進行一次深度或廣度優(yōu)先搜索卵洗，便可以求得任意兩點之間的最短路徑∶诌洌可是還有沒有別的方法呢过蹂？

我們來想一想，根據(jù)我們以往的經(jīng)驗酪夷，如果要讓任意兩點（例如從頂點 a 點到頂點 b）之間的路程變短，只能引入第三個點（頂點 k）孽惰，并通過這個頂點 k 中轉即 a->k->b晚岭，才可能縮短原來從頂點 a 點到頂點 b 的路程。那么這個中轉的頂點 k 是 1~n 中的哪個點呢勋功？甚至有時候不只通過一個點坦报，而是經(jīng)過兩個點或者更多點中轉會更短，即 a->k1->k2b->或者 a->k1->k2…->k->i…->b狂鞋。比如上圖中從 4 號城市到 3 號城市（4->3）的路程 e[4][3]原本是 12片择。如果只通過 1 號城市中轉（4->1->3），路程將縮短為 11（e[4][1]+e[1][3]=5+6=11）骚揍。其實 1 號城市到 3 號城市也可以通過 2 號城市中轉字管，使得 1 號到 3 號城市的路程縮短為 5（e[1][2]+e[2][3]=2+3=5）啰挪。所以如果同時經(jīng)過 1 號和 2 號兩個城市中轉的話，從 4 號城市到 3 號城市的路程會進一步縮短為 10嘲叔。通過這個的例子亡呵，我們發(fā)現(xiàn)每個頂點都有可能使得另外兩個頂點之間的路程變短。好硫戈，下面我們將這個問題一般化锰什。

當任意兩點之間不允許經(jīng)過第三個點時，這些城市之間最短路程就是初始路程丁逝，如下汁胆。

如現(xiàn)在只允許經(jīng)過 1 號頂點，求任意兩點之間的最短路程霜幼，應該如何求呢嫩码？只需判斷 e[i][1]+e[1][j]是否比 e[i][j]要小即可。e[i][j]表示的是從 i 號頂點到 j 號頂點之間的路程辛掠。e[i][1]+e[1][j]表示的是從 i 號頂點先到 1 號頂點谢谦，再從 1 號頂點到 j 號頂點的路程之和。其中 i 是 1~n 循環(huán)萝衩，j 也是 1~n 循環(huán)回挽，代碼實現(xiàn)如下。

for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if ( e[i][j] > e[i][1]+e[1][j] )
              e[i][j] = e[i][1]+e[1][j];
        }
    }

在只允許經(jīng)過 1 號頂點的情況下猩谊，任意兩點之間的最短路程更新為：

通過上圖我們發(fā)現(xiàn)：在只通過 1 號頂點中轉的情況下千劈，3 號頂點到 2 號頂點（e[3][2]）、4 號頂點到 2 號頂點（e[4][2]）以及 4 號頂點到 3 號頂點（e[4][3]）的路程都變短了牌捷。

接下來繼續(xù)求在只允許經(jīng)過 1 和 2 號兩個頂點的情況下任意兩點之間的最短路程墙牌。如何做呢？我們需要在只允許經(jīng)過 1 號頂點時任意兩點的最短路程的結果下暗甥，再判斷如果經(jīng)過 2 號頂點是否可以使得 i 號頂點到 j 號頂點之間的路程變得更短喜滨。即判斷 e[i][2]+e[2][j]是否比 e[i][j]要小，代碼實現(xiàn)為如下撤防。

//經(jīng)過1號頂點
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if (e[i][j] > e[i][1]+e[1][j])  e[i][j]=e[i][1]+e[1][j];
    //經(jīng)過2號頂點
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if (e[i][j] > e[i][2]+e[2][j])  e[i][j]=e[i][2]+e[2][j];

在只允許經(jīng)過 1 和 2 號頂點的情況下虽风，任意兩點之間的最短路程更新為：

通過上圖得知，在相比只允許通過 1 號頂點進行中轉的情況下寄月，這里允許通過 1 和 2 號頂點進行中轉辜膝，使得 e[1][3]和 e[4][3]的路程變得更短了。

同理漾肮，繼續(xù)在只允許經(jīng)過 1厂抖、2 和 3 號頂點進行中轉的情況下，求任意兩點之間的最短路程克懊。任意兩點之間的最短路程更新為：

最后允許通過所有頂點作為中轉忱辅，任意兩點之間最終的最短路程為：

for(k=1;k<=n;k++)
       for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
               if(e[i][j]>e[i][k]+e[k][j])
                    e[i][j]=e[i][k]+e[k][j];

這段代碼的基本思想就是：最開始只允許經(jīng)過 1 號頂點進行中轉耕蝉，接下來只允許經(jīng)過 1 和 2 號頂點進行中轉……允許經(jīng)過 1~n 號所有頂點進行中轉崔梗，求任意兩點之間的最短路程。用一句話概括就是：從 i 號頂點到 j 號頂點只經(jīng)過前k號點的最短路程垒在。其實這是一種“動態(tài)規(guī)劃”的思想蒜魄，關于這個思想我們將在《啊哈！算法 2——偉大思維閃耀時》在做詳細的討論场躯。下面給出這個算法的完整代碼：
這段代碼的基本思想就是：最開始只允許經(jīng)過 1 號頂點進行中轉谈为，接下來只允許經(jīng)過 1 和 2 號頂點進行中轉……允許經(jīng)過 1~n 號所有頂點進行中轉，求任意兩點之間的最短路程踢关。用一句話概括就是：從 i 號頂點到 j 號頂點只經(jīng)過前k號點的最短路程伞鲫。其實這是一種“動態(tài)規(guī)劃”的思想，關于這個思想我們將在《啊哈签舞！算法 2——偉大思維閃耀時》在做詳細的討論秕脓。下面給出這個算法的完整代碼：

    #include <stdio.h>
    int main()
    {
        int e[10][10],k,i,j,n,m,t1,t2,t3;
        int inf=99999999; //用inf(infinity的縮寫)存儲一個我們認為的正無窮值
        //讀入n和m，n表示頂點個數(shù)，m表示邊的條數(shù)
        scanf("%d %d",&n,&m);

        //初始化
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i==j) e[i][j]=0;
                  else e[i][j]=inf;
        //讀入邊
        for(i=1;i<=m;i++)
        {
            scanf("%d %d %d",&t1,&t2,&t3);
            e[t1][t2]=t3;
        }

        //Floyd-Warshall算法核心語句
        for(k=1;k<=n;k++)
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                    if(e[i][j]>e[i][k]+e[k][j] )
                        e[i][j]=e[i][k]+e[k][j];

        //輸出最終的結果
        for(i=1;i<=n;i++)
        {
         for(j=1;j<=n;j++)
            {
                printf("%10d",e[i][j]);
            }
            printf("\n");
        }

        return 0;
    }

有一點需要注意的是：如何表示正無窮。我們通常將正無窮定義為 99999999陋桂，因為這樣即使兩個正無窮相加市咆，其和仍然不超過 int 類型的范圍（C 語言 int 類型可以存儲的最大正整數(shù)是 2147483647）蟹略。在實際應用中最好估計一下最短路徑的上限，只需要設置比它大一點既可以。例如有 100 條邊，每條邊不超過 100 的話拐辽，只需將正無窮設置為 10001 即可。如果你認為正無窮和其它值相加得到一個大于正無窮的數(shù)是不被允許的話擦酌，我們只需在比較的時候加兩個判斷條件就可以了俱诸，請注意下面代碼中帶有下劃線的語句。

//Floyd-Warshall算法核心語句
    for(k=1;k<=n;k++)
       for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
            if(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])
                e[i][j]=e[i][k]+e[k][j];

上面代碼的輸入數(shù)據(jù)樣式為：

4 8
    1 2 2
    1 3 6
    1 4 4
    2 3 3
    3 1 7
    3 4 1
    4 1 5
    4 3 12

第一行兩個數(shù)為 n 和 m赊舶，n 表 示頂點個數(shù)睁搭，m 表示邊的條數(shù)。
接下來 m 行锯岖，每一行有三個數(shù) t1介袜、t2 和 t3甫何，表示頂點 t1 到頂點 t2 的路程是 t3出吹。
得到最終結果如下：

通過這種方法我們可以求出任意兩個點之間最短路徑。它的時間復雜度是 O(N3)辙喂。令人很震撼的是它竟然只有五行代碼捶牢，實現(xiàn)起來非常容易鸠珠。正是因為它實現(xiàn)起來非常容易，如果時間復雜度要求不高秋麸，使用 Floyd-Warshall 來求指定兩點之間的最短路或者指定一個點到其余各個頂點的最短路徑也是可行的渐排。當然也有更快的算法，請看下一節(jié)：Dijkstra 算法灸蟆。

另外需要注意的是：Floyd-Warshall 算法不能解決帶有“負權回路”（或者叫“負權環(huán)”）的圖驯耻，因為帶有“負權回路”的圖沒有最短路。例如下面這個圖就不存在 1 號頂點到 3 號頂點的最短路徑炒考。因為 1->2->3->1->2->3->…->1->2->3 這樣路徑中可缚，每繞一次 1->-2>3 這樣的環(huán)，最短路就會減少 1斋枢，永遠找不到最短路帘靡。其實如果一個圖中帶有“負權回路”那么這個圖則沒有最短路。