【問題E09】最短路徑問題(Shortest path)。     [回前頁]

假設有5個朋友的住處分別用a,b,c,d,e來表示。如果任兩點之間有路相通，則會知道距離，例如a-b直通的路徑的距離是10，就用a-b=10表示。b-c直通的路徑的距離是20，就用b-c=20表示。a-c直通的路徑的距離是35，就用a-c=35表示。

現在發生了一件急事，我們希望想從a運送物品到e，並且希望能找出一條最短路徑。來幫他們快速解決緊急事件。要注意的是：任兩點之間的路是雙向，也就是說如果a-b=10則b-a也等於10。

本問題的輸入只有一組樣本，但卻分散在連續的各行，請先自行合併成一行，再作進一步的處理，而且資料是用「起點-終點=距離」的格式，代表某兩點間的距離。而不同兩點距離資料將與前一組資料以逗點分開。

對於該組樣本找出a-e的最短路徑後輸出其值。

【輸入檔案範例1】

a-b=10,b-c=20,a

-c=35,a-e=100,c-e=

20

【輸出檔案範例２】

50

【輸入檔案範例２】

a-b=10,b-c=20,a

-c=35,a-e=100,c-e=

20,c-d=9

,d-e=7

【輸出檔案範例２】

46