圖論-10：最優乘車
描述
H城是一個旅遊勝地，每年都有成千上萬的人前來觀光。為方便遊客，巴士公司在各個旅遊景點及賓館，飯店等地都設置了巴士站並開通了一些單程巴上線路。每條單程巴士線路從某個巴士站出發，依次途經若干個巴士站，最終到達終點巴士站。
一名旅客最近到H城旅遊，他很想去S公園遊玩，但如果從他所在的飯店沒有一路巴士可以直接到達S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站台的另一路巴士,這樣換乘幾次後到達S公園。
現在用整數1,2,…N給H城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號為1，S公園巴士站的編號為N。
寫一個程序，幫助這名旅客尋找一個最優乘車方案,使他在從飯店乘車到S公園的過程中換車的次數最少。
輸入
文件的第一行有兩個數字M和N(1
輸出
文件只有一行。如果無法乘巴士從飯店到達S公園，則輸出"N0"，否則輸出你的程序所找到的最少換車次數，換車次數為0表示不需換車即可到達。
樣例輸入
3 76 74 7 3 62 1 3 5
樣例輸出
2
試題分析：
參考程序1：floyd演算法實現
下面介紹Bellman-Ford演算法：
參考程序2：Bellman-Ford演算法實現
從前面的邊的遍歷時，我們可以看出，實際上每次雖然對所有邊都進行了枚舉，但實際上，參與枚舉運算的邊僅僅只有能經過u點到達v點的邊，其他邊完全沒有參與鬆弛運算。
如：第一次遍歷邊，我們找的是u=1對應能到達的點v=3,5
第二次遍歷邊，我們找的是u=3對應能到達的點v=6,5
在鬆弛時，我們考慮的是v0=1直達6,5點是否比經過u=3到達6,5點的距離更短？如果是，則更新dis數組。
由此，我們可以得知，我們只需要將每個點對應能出去的邊存下來，只要對每個點的每條邊進行枚舉，即可得到最短路徑。
參考程序3：Bellman-Ford演算法實現（鄰接表）
圖文編輯：陳鷗輝老師
