d915. 3. 洗街車路線問題
Tags :
Accepted rate : 101人/108人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-22 17:50

Content

  市政府派出一輛洗街車欲清洗甲區域的街道,甲區域有 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 單位。

 

Input
  第一行有三個數字,連續兩個數字之間以空白符號做區格。第一個數字 N (2 <= N <= 1500) 代表圖形的節點個數;第二個數字 M (1 <= M <= N( N-1 )/2) 代表圖形的連結線個數 (任兩個加水站之間最多只有一條連結線);第三個數字則代表起始站名稱。從第二行起連續有 M 行,表示 M 條連結線,每行有三個數字,連續兩個數字之間以空白符號做區格:前二個數字代表連結線的兩個端點,第三個數字代表連結線的權重。輸入保證任兩個加水站之間都有路徑相連,Nodd 為偶數且0 <= Nodd <= 14。
Output
  輸出一個數字代表洗街車所花費的最短時間。
Sample Input #1
輸入範例 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
Sample Output #1
輸出範例 1: 
64

輸出範例 2:
l8

輸出範例3 : 
20
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1K
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
Hint :
Tags:
出處:
99學年度全國資訊學科能力競賽 [管理者: pcshic (PCSHIC) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」