d005. Food Leopard - 花中程式設計挑戰系統

Content

2080年，地球經過多次劇變，每個大城市已經分成好幾個無法直接透過地面交通工具可以到達的區域，不過因為科技發達，要在無法直接相連的區域移動還是可以透過傳送點在不同的區域當中移動；但因為建造一個傳送點所要花費的成本太高，因此每個區域都僅有一個地點有建置傳送點，要到達這個區域的其他地點，都必須先傳送到這個唯一的傳送點，再透過地面交通工具前往其他地點。

大城市當中每個區域都有許多不同的美食，有一家公司名為Food Leopard的公司負責提供美食外送服務，外送人員因為成本關係僅能透過地面交通工具來送貨，交通工具所需要花費的所有運送燃料成本都由公司支出，但因為先前公司有投資傳送點的建置，因此透過傳送點傳送交通工具的成本為0，公司委託你負責開發Leopard Food Delivery APP，希望你能透過這個App告知送貨人員要怎麼樣運送可以將所需的燃料成本降到最低。

公司每次交給每個送貨人員的訂單都是隨機分配的，但因為送達時間有規定，因此必須按照指定順序到達不同的送貨地點，請你根據每筆訂單的指定順序計算出每筆訂單完成所需要的最低燃料成本。

Input

輸入資料總共有四行
第一行有一個數字N，代表這個大城市共有N個地點，地點以編號1~N表達，地點編號與區域沒有關係，但每個區域的傳送點會是該區域編號最小的地點，其中10<=N<=1000

第二行有一個數字M，代表接下來將會有 M筆資料，其中 5<=M<= N(N-1)/2。

第三行開始有M行資料，每行資料皆由三個數字a b c組成，a與b 代表兩個地點的編號，c 代表在這兩個地點間移動所需要花費的燃料成本，其中 10 <=c<=100，在這M筆資料當中互相相連的地點才能夠透過地面交通工具前往，不相連的地點代表身處不同區域，要到不同的區域必須先到達傳送點，先進行傳送到該區域的傳送點後，才能繼續透過地面交通工具前往其他地點。

第四行由多個空白隔開的數字組成，第一個數字代表這筆訂單指定傳送地點的總數量 k ，接下來 k 個數字便是每筆訂單規定的指定地點到達順序，送貨員會從第一個地點出發，最後回到最後一個地點交回交通工具並完成訂單，其中 2<=k<=100000。

Output

針對該筆訂單，請輸出完成訂單所需要的最低燃料成本。

Sample Input

10
10
2 7 20
2 10 20
1 6 30
6 5 10
1 5 50
5 9 20
1 9 20
4 8 30
4 3 20
3 8 30
5 1 5 6 8 7

Sample Output

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (12%): 1.0s , <1K
公開測資點#1 (12%): 1.0s , <1K
公開測資點#2 (12%): 1.0s , <1K
公開測資點#3 (12%): 1.0s , <1K
公開測資點#4 (13%): 1.0s , <1K
公開測資點#5 (13%): 1.0s , <1M
公開測資點#6 (13%): 1.0s , <1M
公開測資點#7 (13%): 1.0s , <1K

Hint ：

Tags:

出處:

[管理者：

zero (管理員)

]

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

公司每次交給每個送貨人員的訂單都是隨機分配的，但因為送達時間有規定，因此必須按照指定順序到達不同的送貨地點，請你根據每筆訂單的指定順序計算出每筆訂單完成所需要的最低燃料成本。

輸入資料總共有四行第一行有一個數字N，代表這個大城市共有N個地點，地點以編號1~N表達，地點編號與區域沒有關係，但每個區域的傳送點會是該區域編號最小的地點，其中10<=N<=1000

第二行有一個數字M，代表接下來將會有 M筆資料， 其中 5<=M<= N(N-1)/2。

針對該筆訂單，請輸出完成訂單所需要的最低燃料成本。

輸入資料總共有四行
第一行有一個數字N，代表這個大城市共有N個地點，地點以編號1~N表達，地點編號與區域沒有關係，但每個區域的傳送點會是該區域編號最小的地點，其中10<=N<=1000

第二行有一個數字M，代表接下來將會有 M筆資料，其中 5<=M<= N(N-1)/2。