圖論是計算機科學的一個重要分支，至少可追朔到十八世紀尤拉(Euler)所解決著名的七橋問題(Seven Bridges of Königsberg)，許多最佳化問題都涉及到如何有效處理圖形問題。
本問題要求計算郵差徒步送信的最短路徑。
The Problem
給定數條街道的資訊(以十字路口連接不同道路)，你的程式必須計算走過全部的街道所需的最短距離，路徑的起點與終點必須一致。
你可以想像在現實世界中有一位郵差，他先把車開到十字路口之後再走路到各個巷弄把附近需要遞送的郵件一一送完，之後再走到車子所在的路口開往下個地點送信。
行經一條街道的距離直接等於街道的長度(不管該道路有沒有信要送，都必須走完整條道路的距離)。
本問題中，在路口交會的所有道路數目被稱做該路口的"層級"(degree)，最多只會有兩個路口的"層級"為奇數，其他所有路口皆為偶數，也就是只會有偶數條道路在此路口交會。
The Input
一組輸入資料最少會有一條以上的道路，每條道路都有其名稱，每條路一列，直到遇見名稱為"deadend"的輸入，注意deadend並不包含在該組道路裡面。路名的第一個字元與最後一個字元表示該街道兩端的路口，街道名稱的長度表示該街道的距離長度，所有路名皆以小寫字母表示。
例如，名稱為foo的道路表示它兩端的路口為 f 與 o，且長度為3，而名稱為computer的道路兩端路口為 c 與 r，長度為8。不會有路名的頭尾字元是相同的，且最多只會有一條道路直接連接任兩個路口。另外就如之前提及，所連接的道路數量為奇數的路口最多只會有兩個。所有的路口都是互相連通的。
The Output
針對每組道路資訊，請輸出郵差走過所有該組道路最少一次的最短路徑長度，請每組依序輸出。
Sample Input
one
two
three
deadend
mit
dartmouth
linkoping
tasmania
york
emory
cornell
duke
kaunas
hildesheim
concord
arkansas
williams
glasgow
deadend
Sample Output
11
114
沒有留言:
張貼留言