1028 . 旅遊規劃問題
TopCoder
Description
有一個旅行社想要開發一個旅遊規劃程式來幫客戶計算出其選定之觀光景點的最短交通路徑。所有的觀光景點（不超過13個景點）可以形成一個景點圖。
此系統可以讓客戶選擇要玩的觀光景點（最少兩個，不超過總共景點數）。其中第一個為出發的景點，系統即自動規劃出可以走完所有指定觀光景點的最短路徑。其所規劃的路徑可以重覆經過同一個觀景點，且可任意排列參觀的次序（起點除外）。
Input Format
首先有一個正整數 $n$（$2 \le n \le \textcolor{red}{13}$），代表總共景點數，這些景點的編號由 $0$ 到 $n-1$。接下來有個整數 $m$，代表有幾條邊。接下來 $m$ 行，每行有三個數代表一條邊，第一、第二個數代表這條邊連結哪兩個點，第三個數代表這條邊的長度。再這之後有一個數字 $k$，代表想去的景點有 $k$ 個（包括起點），下一行有 $k$ 個數，代表 $k$ 個想去的景點的編號，其中第一個數為起點。
Output Format
首先請輸出最短的行程總長為多少，再來請輸出依序要經過哪些景點。若有多條最佳解，請輸出字典順序最小的那組。
Sample Input 1
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
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 1
Minimum travel distance: 18
Travel route: 2 6 8 6 4 5 4 3 7
Travel route: 2 6 8 6 4 5 4 3 7
Hints
輸入的數值限制有稍作更改，請留意 :)
Problem Source
原TIOJ1028 / 96建中校內資訊能力競賽(prob5)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 11 |
| 2 | 1 | 11 |
| 3 | 2 | 11 |
| 4 | 3 | 11 |
| 5 | 4 | 11 |
| 6 | 5 | 11 |
| 7 | 6 | 11 |
| 8 | 7 | 11 |
| 9 | 8 | 12 |