102705: [AtCoder]ABC270 F - Transportation

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：7 Solved：0

Description

Score : $500$ points

Problem Statement

The Republic of AtCoder has $N$ islands. Initially, none of the islands has an airport or harbor, and there is no road between any two of them. Takahashi, the king, will provide some means of transportation between these islands. Specifically, he can do the following operations any number of times in any order.

  • Choose an integer $i$ such that $1\leq i\leq N$ and pay a cost of $X_i$ to build an airport on island $i$.
  • Choose an integer $i$ such that $1\leq i\leq N$ and pay a cost of $Y_i$ to build a harbor on island $i$.
  • Choose an integer $i$ such that $1\leq i\leq M$ and pay a cost of $Z_i$ to build a road that bidirectionally connects island $A_i$ and island $B_i$.

Takahashi's objective is to make it possible, for every pair of different islands $U$ and $V$, to reach island $V$ from island $U$ when one can perform the following actions any number of times in any order.

  • When islands $S$ and $T$ both have airports, go from island $S$ to island $T$.
  • When islands $S$ and $T$ both have harbors, go from island $S$ to island $T$.
  • When islands $S$ and $T$ are connected by a road, go from island $S$ to island $T$.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

  • $2 \leq N \leq 2\times 10^5$
  • $1 \leq M \leq 2\times 10^5$
  • $1\leq X_i\leq 10^9$
  • $1\leq Y_i\leq 10^9$
  • $1\leq A_i<B_i\leq N$
  • $1\leq Z_i\leq 10^9$
  • $(A_i,B_i)\neq (A_j,B_j)$, if $i\neq j$.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$X_1$ $X_2$ $\ldots$ $X_N$
$Y_1$ $Y_2$ $\ldots$ $Y_N$
$A_1$ $B_1$ $Z_1$
$A_2$ $B_2$ $Z_2$
$\vdots$
$A_M$ $B_M$ $Z_M$

Output

Print the minimum total cost Takahashi needs to pay to achieve his objective.

Sample Input 1

4 2
1 20 4 7
20 2 20 3
1 3 5
1 4 6

Sample Output 1

16

Takahashi will build the following infrastructure.

  • Pay a cost of $X_1=1$ to build an airport on island $1$.
  • Pay a cost of $X_3=4$ to build an airport on island $3$.
  • Pay a cost of $Y_2=2$ to build a harbor on island $2$.
  • Pay a cost of $Y_4=3$ to build a harbor on island $4$.
  • Pay a cost of $Z_2=6$ to build a road connecting island $1$ and island $4$.

Then, the objective will be achieved at a cost of $16$. There is no way to achieve the objective for a cost of $15$ or less, so $16$ should be printed.

Sample Input 2

3 1
1 1 1
10 10 10
1 2 100

Sample Output 2

3

It is not mandatory to build all three types of facilities at least once.

Sample Input 3

7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

Sample Output 3

160

Input

题意翻译

有 $n$ 个点，如下操作： - 对于 $1\le i\le n$，可以花 $x_i$ 的贡 $i$ 号点建一个机场 . - 对于 $1\le i\le n$，可以花 $y_i$ 的贡献在 $i$ 号点建一个港口 . - 对于 $1\le i\le n$，可以花 $z_i$ 的贡献在 $a_i$ 号点到 $b_i$ 号点连一条无向边 . 如果两个点 $u,v$ 满足下列条件之一，则 $u,v$ 可以互相到达： - $u,v$ 都有机场 . - $u,v$ 都有港口 . - $u$ 到 $v$ 有边 . 问至少花多少代价才能让所有点连通 . $1\le n,m\le 2\times 10^5$，$1\le x_i,y_i,z_i\le 10^9$ .

Output

得分：500分

问题描述

AtCoder共和国共有$N$个岛屿。 最初，没有任何一个岛屿有机场或港口，也没有两个岛屿之间有任何道路。 国王Takahashi将为这些岛屿提供一些交通工具。 具体来说，他可以在任意顺序任意次数地执行以下操作。

  • 选择一个整数$i$，使得$1\leq i\leq N$，并支付费用$X_i$在岛屿$i$上建造一个机场。
  • 选择一个整数$i$，使得$1\leq i\leq N$，并支付费用$Y_i$在岛屿$i$上建造一个港口。
  • 选择一个整数$i$，使得$1\leq i\leq M$，并支付费用$Z_i$建造一条双向连接岛屿$A_i$和岛屿$B_i$的道路。

Takahashi的目标是使得，对于每一对不同的岛屿$U$和$V$，在可以任意次数地执行以下操作的情况下，能够从岛屿$U$到达岛屿$V$。

  • 当岛屿$S$和$T$都有机场时，从岛屿$S$到岛屿$T$。
  • 当岛屿$S$和$T$都有港口时，从岛屿$S$到岛屿$T$。
  • 当岛屿$S$和$T$由一条道路连接时，从岛屿$S$到岛屿$T$。

找出Takahashi需要支付的最低总费用，以实现他的目标。

约束条件

  • $2 \leq N \leq 2\times 10^5$
  • $1 \leq M \leq 2\times 10^5$
  • $1\leq X_i\leq 10^9$
  • $1\leq Y_i\leq 10^9$
  • $1\leq A_i<B_i\leq N$
  • $1\leq Z_i\leq 10^9$
  • $(A_i,B_i)\neq (A_j,B_j)$，如果$i\neq j$。
  • 输入中的所有值都是整数。

输入

输入从标准输入给出以下格式：

$N$ $M$
$X_1$ $X_2$ $\ldots$ $X_N$
$Y_1$ $Y_2$ $\ldots$ $Y_N$
$A_1$ $B_1$ $Z_1$
$A_2$ $B_2$ $Z_2$
$\vdots$
$A_M$ $B_M$ $Z_M$

输出

打印Takahashi实现他的目标需要支付的最低总费用。

样例输入1

4 2
1 20 4 7
20 2 20 3
1 3 5
1 4 6

样例输出1

16

Takahashi将建造以下基础设施。

  • 支付费用$X_1=1$在岛屿$1$上建造一个机场。
  • 支付费用$X_3=4$在岛屿$3$上建造一个机场。
  • 支付费用$Y_2=2$在岛屿$2$上建造一个港口。
  • 支付费用$Y_4=3$在岛屿$4$上建造一个港口。
  • 支付费用$Z_2=6$建造一条连接岛屿$1$和岛屿$4$的道路。

然后，以$16$的费用实现目标。 没有以$15$或更低的费用实现目标的方法，因此应打印$16$。

样例输入2

3 1
1 1 1
10 10 10
1 2 100

样例输出2

3

不一定要至少建造三种设施中的一种。

样例输入3

7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

样例输出3

160

Source/Category

加入题单

上一题 下一题 算法标签：