你剛搬進(jìn)一套新公寓，有一長(zhǎng)串你需要買(mǎi)的東西。不幸的是，買(mǎi)這么多東西需要去很多不同的商店。你想盡量減少購(gòu)買(mǎi)所需物品所需的駕駛時(shí)間。

你的城市被組織成一組由道路連接的十字路口。你的房子和每家商店都在某個(gè)十字路口。你的任務(wù)是找到從你家出發(fā)的最短路線(xiàn)，參觀所有你需要購(gòu)物的商店，然后返回你家。

輸入

輸入的第一行包含一個(gè)整數(shù)，即接下來(lái)的測(cè)試用例數(shù)。每個(gè)測(cè)試用例以包含兩個(gè)整數(shù)N和M的行開(kāi)始，這兩個(gè)整數(shù)分別是城市中路口和道路的數(shù)量。每個(gè)整數(shù)都在1到100000之間，包括。交叉點(diǎn)的編號(hào)從0到N-1。你的房子在0號(hào)路口。接下來(lái)是M行，每一行包含三個(gè)整數(shù)X、Y和D，表示X和Y的交叉點(diǎn)由一條長(zhǎng)度為D的雙向道路連接。接下來(lái)的一行包含一個(gè)整數(shù)S，即你需要訪(fǎng)問(wèn)的商店的數(shù)量，包括1到10個(gè)。隨后的S行每一個(gè)都包含一個(gè)整數(shù)，指示每個(gè)商店所在的交叉點(diǎn)。從你家到所有商店都是可能的。

輸出

對(duì)于每個(gè)測(cè)試用例，輸出一行，其中包含一個(gè)整數(shù)，即從您的房子出發(fā)、訪(fǎng)問(wèn)所有商店和返回您的房子的最短購(gòu)物旅程的長(zhǎng)度。

樣例輸入

1

4 - 6

0 1 1

1 2 1

1 2 3

3 0 1

0 2 5

1 3 5

3

1

2

3

樣例輸出

4

參考代碼：
https://blog.csdn.net/haojunliang_hao/article/details/76577427

總結(jié)

以上是生活随笔為你收集整理的（最短路）Shopping的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。