← 返回题目列表

AtCoder · arc029_3

C. 高桥和国家

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

問題文

高桥在游戏中统治国家。

为了国家 N 城市和M 有一条书路。每条路径都是 2 它直接连接两个不同的城市,沿途没有其他城市。另外,哪个 2 即使对于两个城市来说,也没有直接连接它们的道路。 1 一。

起初,所有道路都没有铺好,所有城市都没有贸易站。

高桥决定为国家的发展铺路、建立贸易站。

如果任何城市满足以下任何条件,则称一个国家处于“良好状况”。

  • 城市中有一个贸易站。
  • 虽然一个城市没有贸易站,但可以从该城市前往另一个有贸易站的城市,但只能通过铺好的道路。

在城市 1 如果要将其更改为输出最多为 N 在路上直到 它们的编号最大为 1 如果要将其更改为输出最多为 M 。城市 在 i 设立交易站需要金币。 需要 c_i 页。还有,路 需要金币才能铺好 i 需要 r_i 页。

我没有很多金币,所以我想尽量减少让国家进入“好状态”所需的金币数量。

编写一个程序来找出所需的最少金币数量。


入力

输入将以以下形式通过标准输入给出。

N M
c_1
c_2
:
c_N
a_1 b_1 r_1
a_2 b_2 r_2
:
a_M b_M r_M
  • 1 行中,2 整数 编写一个程序来查找 N (2 ≦ N ≦ 100,000) 和 将其放在 M (1 ≦ M ≦ 200,000) 用空格分隔。这意味着这座城市 N 这条路是 M 代表有一本书。
  • 2 在 N 行包含一个表示有关城市的信息的整数。 给出了 c_i (1 ≦ c_i ≦ 1,000,000,000) 。这是一座城市 表示需要 i 设立交易站需要金币。 需要 c_i 件。
  • N+2 在 M 线表示有关道路的信息。 3 整数 编写一个程序来查找 a_i, b_i (1 ≦ a_i < b_i ≦ N), r_i (1 ≦ r_i ≦ 1,000,000,000) 用空格分隔。这就是路 i 是一座城市 a_i 和城市 b_i 在终点,需要铺设 r_i 表示需要。

部分点

针对此问题设置了部分分数。

  • N ≦ 8 和 满足 M ≦ 10 的数据集 如果您正确回答 1 , 如果您对10 分被给予。
  • N ≦ 12 和 满足 M ≦ 66 的数据集 如果您正确回答 2 的回答正确,除上述之外, 20 分被给予。
  • N ≦ 3,000 和 满足 M ≦ 6,000 的数据集 如果您正确回答 3 的回答正确,除上述之外, 30 分被给予。
  • 没有附加约束的数据集 4 的回答正确,除上述之外, 40 分被给予。

出力

定义使一个国家进入“良好状态”的最低可能总成本。 在 1 行输出。还在输出末尾添加换行符。


入力例1

7 8
40
50
30
70
70
80
80
1 2 40
1 3 50
1 4 60
2 5 90
3 4 80
4 5 110
5 6 60
6 7 50

出力例1

350

城市及道路布局如下图。

在以下条件下建立交易站并铺设道路。 在

  • 都市 1 设立一个交易站。设立交易站需要金币。 连接 40 页。
  • 都市 3 设立一个交易站。设立交易站需要金币。 连接 30 页。
  • 都市 5 设立一个交易站。设立交易站需要金币。 连接 70 页。
  • 道 1 (都市 1 和城市 2 )。人行道上的金币 40 页。
  • 道 3 (都市 1 和城市 4 )。人行道上的金币 60 页。
  • 道 7 (都市 5 和城市 6 )。人行道上的金币 60 页。
  • 道 8 (都市 6 和城市 7 )。人行道上的金币 50 页。

城市和道路的最终状态如下所示。在这里,有贸易站的城市显示为双边界,铺好的道路显示为双线。

在这种情况下,国家可以说处于“良好状态”。事实上, 交易站位于

  • 都市 1 。
  • 都市 2 中没有贸易站,但有一条柏油路。 通过 1 拥有贸易站的城市 您可以移至 1 。 一条铺有
  • 都市 3 。
  • 都市 4 中没有贸易站,但有一条柏油路。 通过 3 拥有贸易站的城市 您可以移至 1 。 一条铺有
  • 都市 5 。
  • 都市 6 中没有贸易站,但有一条柏油路。 通过 7 拥有贸易站的城市 您可以移至 5 。 一条铺有
  • 都市 7 中没有贸易站,但有一条柏油路。 通过 7 的路 8 拥有贸易站的城市 您可以移至 5 。 一条铺有

。金币 需要 40 + 30 + 70 + 40 + 60 + 60 + 50 = 350 页。


入力例2

3 3
50
50
50
1 2 60
1 3 60
2 3 60

出力例2

150

在每个城市都有一个交易站会更便宜。


入力例3

5 7
80
70
60
50
40
1 3 20
1 4 70
1 5 30
2 3 30
2 4 90
3 4 40
4 5 80

出力例3

160