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 公园的花费总和的最小值。 ## 输入格式输入标准如下： - 第一行为三个以空格分开的整数 $ N,M,C $ ，分别表示广场共有 $ N $ 个，道路有 $ M $ 条，而 $ C $ 为与修筑地下通道花费有关的量； - 接下来 $ M $ 行中的第 $ i $ 行 $ (1 \leq i \leq M) $ 为三个以空格分开的整数 $ A_i,B_i,D_i $ 。表示第 $ i $ 条道路连接广场 $ A_i $ 和广场 $ B_i $ ，其长度为 $ D_i $ 。 ## 输出格式输出一行一个整数：修缮 JOI 公园的花费总和的最小值。 ## 样例 #### 输入样例 1 ```plain 5 5 2 2 3 1 3 1 2 2 4 3 1 2 4 2 5 5 ``` #### 输出样例 1 ```plain 14 ``` #### 样例说明 1 对于输入样例 $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 对于输入样例 $ 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 对于输入样例 $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) $ - 输入数据保证任意两个广场之间一定有道路连接（直接或间接）。感谢@ミク提供的翻译

题目描述

[problemUrl]: https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_c 20XX 年に IOI 国で行われるオリンピックに備え，IOI 国にある JOI 公園を整備することになった．JOI公園には $ N $ 個の広場があり，広場には $ 1 $ から $ N $ の番号がついている．広場を繋ぐ $ M $ 本の道があり，道には $ 1 $ から $ M $ の番号がついている．道 $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) は広場 $ A_i $ と広場 $ B_i $ を双方向に繋いでおり，長さは $ D_i $ である．どの広場からどの広場へもいくつかの道を辿って行くことができる．整備計画では，まず，$ 0 $ 以上の整数 $ X $ を選び，広場 $ 1 $ からの距離が $ X $ 以下であるような広場 (広場 $ 1 $ を含む) どうしをすべて相互に地下道で結ぶ．ただし，広場 $ i $ と広場 $ j $ の距離とは，広場 $ i $ から広場 $ j $ に行くときに通る道の長さの和の最小値である．整備計画では地下道の整備コストに関する整数 $ C $ が定まっている．地下道の整備にかかるコストは $ C\ \times\ X $ である．次に，地下道で結ばれた広場どうしを結ぶ道をすべて撤去する．道の撤去にコストはかからない．最後に，撤去されずに残った道をすべて補修する．長さ $ d $ の道を補修するためにかかるコストは $ d $ である．整備計画実施前の JOI 公園には地下道はない．JOI 公園の整備にかかるコストの和の最小値を求めよ．

输入输出格式

输入格式

標準入力から以下のデータを読み込め． - $ 1 $ 行目には，整数 $ N,\ M,\ C $ が空白を区切りとして書かれている．これは，広場が $ N $ 個，道が $ M $ 本あり，地下道の整備コストに関する整数が $ C $ であることを表す． - 続く $ M $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ M $) には，整数 $ A_i,\ B_i,\ D_i $ が空白を区切りとして書かれている．これは，道 $ i $ が広場 $ A_i $ と広場 $ B_i $ を繋ぎ，長さが $ D_i $ であることを表す．

输出格式

標準出力に，JOI 公園の整備にかかるコストの和の最小値を表す整数を $ 1 $ 行で出力せよ． - - - - - -

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

输入样例 #3

输出样例 #3

说明

### 課題 JOI 公園の広場の情報と，地下道の整備コストに関する整数が与えられたとき，JOI 公園の整備にかかるコストの和の最小値を求めるプログラムを作成せよ． - - - - - - ### 制限すべての入力データは以下の条件を満たす． - $ 2\ \leqq\ N\ \leqq\ 100\,000 $． - $ 1\ \leqq\ M\ \leqq\ 200\,000 $． - $ 1\ \leqq\ C\ \leqq\ 100\,000 $． - $ 1\ \leqq\ A_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 1\ \leqq\ B_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ A_i\ \neq\ B_i $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ (A_i,\ B_i)\ \neq\ (A_j,\ B_j) $ および $ (A_i,\ B_i)\ \neq\ (B_j,\ A_j) $ ($ 1\ \leqq\ i\ <\ j\ \leqq\ M $)． - $ 1\ \leqq\ D_i\ \leqq\ 100\,000 $ ($ 1\ \leqq\ i\ \leqq\ M $)． - 与えられる入力データにおいては，どの広場からどの広場へもいくつかの道を辿ることにより行けることが保証されている． ### 小課題 #### 小課題 1 \[15 点\] 以下の条件を満たす． - $ N\ \leqq\ 100 $． - $ M\ \leqq\ 200 $． - $ C\ \leqq\ 100 $． - $ D_i\ \leqq\ 10 $ ($ 1\ \leqq\ i\ \leqq\ M $)． #### 小課題 2 \[45 点\] 以下の条件を満たす． - $ N\ \leqq\ 100 $． - $ M\ \leqq\ 4\,000 $． #### 小課題 3 \[40 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 この入力例では，$ X\ =\ 3 $ として，広場 $ 1 $ からの距離が $ 3 $ 以下であるような広場 (広場 $ 1 $，広場 $ 2 $，広場 $ 3 $) どうしをすべて相互に地下道で結んだとき，整備にかかるコストの和は $ 2\ \times\ 3\ +\ 3\ +\ 5\ =\ 14 $ となる．これが最小値である． - - - - - - ### Sample Explanation 2 この入力例では，$ X\ =\ 0 $ のとき整備にかかるコストの和が最小になる． - - - - - - ### Sample Explanation 3 この入力例では，$ X\ =\ 5 $ としてすべての広場を相互に地下道で結んだとき，整備にかかるコストの和が最小になる．