← 返回题目列表

AtCoder · joi2015ho_c

C. JOI 公园

中文机器翻译题面 查看原题

配点: 100 点

为了准备在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 公园所需成本总和的最小值。

課題

给定 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 行。


制限

所有输入数据满足以下条件。

  • 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 点]

没有其他限制。


入力例 1

5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5

出力例 1

14

在此输入示例中,X = 3 作为一个正方形 1 的距离是 3 下面是一个正方形(正方形 1,広場 2,広場 3) 当所有建筑物通过地下通道相互连接时,维护费用之和为 2 \times 3 + 3 + 5 = 14 变为。这是最小值。


入力例 2

5 4 10
1 2 3
2 3 4
3 4 3
4 5 5

出力例 2

15

在此输入示例中,X = 0 维护成本总和最小化。


入力例 3

6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5

出力例 3

10

在此输入示例中,X = 5 当所有广场通过地下通道相互连接时,维护成本的总和将最小化。