AT_joi2015ho_c JOI 公園 (JOI Park)

# 「JOI 2014/2015 决赛」JOI 公园 **译自 [JOI 2014/2015 决赛](https://www.ioi-jp.org/joi/2014/2015-ho/index.html) T3「[JOI 公園](https://www.ioi-jp.org/joi/2014/2015-ho/2015-ho.pdf)」** 时值 $ 20\text{XX} $ 年， IOI 国为了给办奥赛做准备，将要修缮 IOI 国中的 JOI 公园。 JOI 公园里有 $ N $ 个广场，这些广场从 $ 1 $ 到 $ N $ 编号。有 $ M $ 条道路连接各个广场，这些道路从 $ 1 $ 到 $ M $ 编号。第 $ i(1 \leq i \leq M) $ 条道路是一条连接第 $ A_i $ 和第 $ B_i $ 个广场的双向边，长度为 $ D_i $ 。任意两个广场间一定有道路（直接或间接）相连。 修缮计划如下：首先，选择一个**自然数** $ X $ ，将和第一个广场距离等于 $ X $ 或在 $ X $ 以下的所有广场（含第一个广场）相互之间连结一条地下通道。广场 $ i $ 和广场 $ j $ 的距离指，从广场 $ i $ 到广场 $ j $ 经过的道路长度总和的最小值。定义 $ C $ 为一个与修筑地下通道花费有关的量（ $ C $ 是整数）。修筑所有地下通道的花费为 $ C\times X $ 。 接下来，撤去已经通过地下通道连接的广场之间的道路。撤去道路的花费不计。 最后，将没有被撤去的道路进行修补，长为 $ d $ 的道路修补的花费为 $ d $ 。 修缮计划实施之前， JOI 公园没有地下通道。请求出 JOI 公园修缮花费总和的最小值。 #### 任务 给出 JOI 公园的广场间道路的情况和 $ C $ 的值，请编写程序求出修缮 JOI 公园的花费总和的最小值。

无

无

对于输入样例 $1$， $ X=3 $ 也就是说，和广场 $ 1 $ 的距离在 $ 3 $ 或以下的广场（广场 $ 1 $ ，广场 $ 2 $ ，广场 $ 3 $ ）互相之间连接一条地下通道。修缮总花费为 $ 2\times 3+3+5=14 $ 。这就是最小值。 #### 输入样例 2 ```plain 5 4 10 1 2 3 2 3 4 3 4 3 4 5 5 ``` #### 输出样例 2 ```plain 15 ``` 对于输入样例 $ 2 $ ，$ X=0 $ 时修缮总花费最小。 #### 输入样例 3 ```plain 6 5 2 1 2 2 1 3 4 1 4 3 1 5 1 1 6 5 ``` #### 输出样例 3 ```plain 10 ``` 对于输入样例 $3$，$ X=5 $ 时所有广场相互间都会连接一条地下通道，此时修缮的花费最小。 对于 $ 15\% $ 的分值： - $ N \leq 100 $ - $ M \leq 200 $ - $ C \leq 100 $ - $ D_i \leq 10 (1 \leq i \leq M) $ 对于另 $ 45\% $ 的分值： - $ N \leq 100 $ - $ M \leq 4000 $ 对于 $ 100\% $ 的分值，所以输入数据满足以下条件： - $ 2 \leq N \leq 10^5 $ - $ 1 \leq M \leq 2\times 10^5 $ - $ 1 \leq C \leq 10^5 $ - $ 1 \leq A_i,B_i \leq N (1 \leq i \leq M) $ - $ A_i\not = B_i (1 \leq i \leq M) $ - $ (A_i,B_i)\not =(A_j,B_j) $ 而且 $ (A_i,B_i)\not =(B_j,A_j) (1 \leq i\lt j \leq M) $ - $ 1 \leq D_i \leq 10^5 (1 \leq i \leq M) $ - 输入数据保证任意两个广场之间一定有道路连接（直接或间接）。 感谢@ミク 提供的翻译