高鐵城市圈對人們的出行、經(jīng)濟(jì)的拉動效果明顯。

每年都會規(guī)劃新的高鐵城市圈建設(shè)。在給定城市數(shù)量，可建設(shè)高鐵的兩城市間的修建成本列表、以及結(jié)合城市商業(yè)價值會固定建設(shè)的兩城市建高鐵。

請你設(shè)計算法，達(dá)到修建城市高鐵的最低成本。注意，需要滿足城市圈內(nèi)城市間兩兩互聯(lián)可達(dá)(通過其他城市中轉(zhuǎn)可達(dá)也屬于滿足條件）。

輸入描述：

1、第一行，包含此城市圈中城市的數(shù)量、可建設(shè)高鐵的兩城市間修建成本列表數(shù)量、必建高鐵的城市列表。三個數(shù)字用空格間隔。

2、可建設(shè)高鐵的兩城市間的修建成本列表，為多行輸入數(shù)據(jù)，格式為3個數(shù)字，用空格分隔，長度不超過1000。

3、 固定要修建的高鐵城市列表，是上面參數(shù)2的子集，可能為多行，每行輸入為2個數(shù)字，以空格分隔。

城市id從1開始編號，建設(shè)成本的取值為正整數(shù)，取值范圍均不會超過1000

輸出描述：

修建城市圈高鐵的最低成本，正整數(shù)。如果城市圈內(nèi)存在兩城市之間無法互聯(lián)，則返回-1。

示例1 ?輸入輸出示例僅供調(diào)試，后臺判題數(shù)據(jù)一般不包含示例

輸入

3 3 0

1 2 10

1 3 100

2 3 50

輸出

60

解釋：

3 3 0城市圈數(shù)量為3，表示城市id分別為1,2,3

1 2 10城市1，2間的高鐵修建成本為10

1 3 100城市1，3間的高鐵修建成本為100

2 3 50城市2，3間的高鐵修建成本為50

滿足修建成本最低，只需要建設(shè)城市1，2間，城市2，3間的高鐵即可，城市1，3之間可通過城市2中轉(zhuǎn)來互聯(lián)。這樣最低修建成本就是60。

示例2 ?輸入輸出示例僅供調(diào)試，后臺判題數(shù)據(jù)一般不包含示例

輸入

3 3 1

1 2 10

1 3 100

2 3 50

1 3

輸出

110

————————————————

版權(quán)聲明：本文為CSDN博主「MISAYAONE」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。

原文鏈接：https://renjie.blog.csdn.net/article/details/128532836

Java 實現(xiàn)：https://renjie.blog.csdn.net/article/details/128532836

Python實現(xiàn)：https://renjie.blog.csdn.net/article/details/128534687

C++ 實現(xiàn)：https://renjie.blog.csdn.net/article/details/128532865

JavaScript實現(xiàn)：https://renjie.blog.csdn.net/article/details/129034836

C語言版本持續(xù)更新中