市政府派出一輛洗街車欲清洗甲區域的街道,甲區域有 N 個加水站,2 <= N <= 1500。為了方便說明,我們將 N 個加水站名稱以正整數 1, 2, …, N 來表示。N 個加水站有街道來連接,使得洗街車可從任一個加水站出發,經由幾條街道抵達另一個加水站。我們可以用圖形來表示這些加水站跟街道的關係:節點表示加水站;而連接結點的連結線則代表連接兩個加水站之間的街道。我們以符號 (I, J) 來表示連接加水站 I 和加水站 J 的連結線,並稱街道 (I, J) 與加水站 I 和加水站 J 相接。每一條連結線 (I, J) 都結合一個權重 w(I, J) 來代表清洗 (I, J) 這條街道所要花費的時間,w(I, J) 為正整數滿足 1 <= w(I, J) <= 888。圖一有 12 個加水站,以數字1 ~ 12 來表示,而街道上的數字則代表清洗此街道所需花費的時間。令 Nodd 代表那些與奇數條街道相接的加水站個數,則甲區域有一個重要特性:Nodd 為偶數且0 <= Nodd <= 14 。在圖一的例子中,Nodd = 8 ,起始加水站為 1。
給定一個起始加水站,請寫一個程式計算洗街車從起始加水站出發,把每條街道都清洗過至少一次,再回到原起始加水站所需花費的最短時間為何?注意:這個城市中所有的街道都是雙向道,洗街車洗街時同一個加水站和街道可被洗街車重複經過。
圖二說明其中一種走法為:1 → 8 → 1 → 9 → 8 一7 → 12 → 6 → 7 → 6 → 5 → 4 → 5 → 11 → 12 → 9 → 10 → 11 → 4 → 3 → 2 → 3 → 10 → 2 → 1,可在 73 單位時間將所有街道都清洗過至少一次,然而此種走法所需的時間並非最短。事實上,此例中花費時間為最短的走法如圖三所示為 l → 8 → 9 → 1 → 9 一8 → 7 → 6 → 12 → 7 → 12 → 6 → 5 → 4 → 11 → 5 → 11 → 4 → 3 → 2 → 10 → 3 → 10 → 11 → 12 → 9 → 10 → 2 → l,所花費時間為 64 單位。
輸入範例 1: 12 20 1 1 2 8 1 8 5 2 3 6 1 9 1 2 10 2 8 9 1 9 10 1 10 3 1 8 7 2 9 12 3 10 11 1 3 4 1 7 12 1 12 11 2 11 4 1 7 6 6 12 6 2 11 5 1 4 5 2 6 5 7 輸入範例 2: 10 9 1 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 輸入範例 3: 20 20 1 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 1 1
輸出範例 1: 64 輸出範例 2: l8 輸出範例3 : 20
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|