TopCoder

User's AC Ratio

78.9% (15/19)

Submission's AC Ratio

23.3% (17/73)

Description

有一個旅行社想要開發一個旅遊規劃程式來幫客戶計算出其選定之觀光景點的最短交通路徑。所有的觀光景點(不超過13個景點)可以形成一個景點圖。
  此系統可以讓客戶選擇要玩的觀光景點(最少兩個,不超過總共景點數)。其中第一個為出發的景點,系統即自動規劃出可以走完所有指定觀光景點的最短路徑。其所規劃的路徑可以重覆經過同一個觀景點,且可任意排列參觀的次序(起點除外)

Input Format

首先有一個正整數n(2<=n<=13),代表總共景點數,這些景點的編號由0到n-1。接下來有個整數m,代表有幾條邊。接下來m行,每行有3個數代表一條邊,第一、第二個數代表這條邊連結哪兩個點,第三個數代表這條邊的長度。再這之後有一個數字k,代表想去的景點有k個(包括起點),下一行有k個數,代表k個想去的景點的編號,其中第一個數為起點。

Output Format

首先請輸出最短的行程總長為多少,再來請輸出依序要經過哪些景點。若有多條最佳解,請輸出字典順序最小的那組

Sample Input

10 16
0 1 12
0 2 40
0 3 15
1 2 3
1 3 1
2 3 25
2 6 2
3 4 2
3 6 15
3 7 3
3 9 3
4 5 2
4 6 1
6 8 3
6 9 20
8 9 16
5
2 3 5 7 8

Sample Output

Minimum travel distance: 18
Travel route: 2 6 8 6 4 5 4 3 7

Hints

輸入的數值限制有稍作更改,請留意:)

Problem Source

原TIOJ1028 / 96建中校內資訊能力競賽(prob5)

Subtasks

For Testdata: 0 ~ 0, Score: 11
For Testdata: 1 ~ 1, Score: 11
For Testdata: 2 ~ 2, Score: 11
For Testdata: 3 ~ 3, Score: 11
For Testdata: 4 ~ 4, Score: 11
For Testdata: 5 ~ 5, Score: 11
For Testdata: 6 ~ 6, Score: 11
For Testdata: 7 ~ 7, Score: 11
For Testdata: 8 ~ 8, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 8000 65536 65536
1 8000 65536 65536
2 8000 65536 65536
3 8000 65536 65536
4 8000 65536 65536
5 8000 65536 65536
6 8000 65536 65536
7 8000 65536 65536
8 8000 65536 65536