题目详情题解（0）讨论（0）提交记录（0）

AT_abc270_f.[ABC270F] Transportation

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 AtCoder 国有 NN 个岛屿，最初每个岛屿上都没有机场和港口，岛屿之间也没有道路。作为国王的高桥君决定为这些岛屿之间提供交通方式。具体来说，高桥君可以无限次地选择并执行以下三种操作之一：

  • 选择满足 1≤i≤N1\leq i\leq N 的 ii，支付费用 XiX_i，在岛屿 ii 上建造机场。
  • 选择满足 1≤i≤N1\leq i\leq N 的 ii，支付费用 YiY_i，在岛屿 ii 上建造港口。
  • 选择满足 1≤i≤M1\leq i\leq M 的 ii，支付费用 ZiZ_i，在岛屿 AiA_i 和岛屿 BiB_i 之间建造一条双向道路。

高桥君的目标是，使得对于任意两个不同的岛屿 UU 和 VV，都可以从岛屿 UU 出发，通过无限次地选择并执行以下三种操作之一，到达岛屿 VV：

  • 如果岛屿 SS 和 TT 都有机场，可以从 SS 移动到 TT。
  • 如果岛屿 SS 和 TT 都有港口，可以从 SS 移动到 TT。
  • 如果存在连接岛屿 SS 和 TT 的道路，可以从 SS 移动到 TT。

请你求出高桥君达成目标所需的最小总费用。

输入格式

输入以如下格式从标准输入读入。

NN MM
X1X_1 X2X_2 …\ldots XNX_N
Y1Y_1 Y2Y_2 …\ldots YNY_N
A1A_1 B1B_1 Z1Z_1
A2A_2 B2B_2 Z2Z_2
⋮\vdots
AMA_M BMB_M ZMZ_M

输出格式

输出高桥君达成目标所需的最小总费用。

输入输出样例

  • 输入#1

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

    输出#1

    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

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 1≤M≤2×1051 \leq M \leq 2\times 10^5
  • 1≤Xi≤1091 \leq X_i \leq 10^9
  • 1≤Yi≤1091 \leq Y_i \leq 10^9
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • 1≤Zi≤1091 \leq Z_i \leq 10^9
  • 若 i≠ji \neq j，则 (Ai,Bi)≠(Aj,Bj)(A_i,B_i) \neq (A_j,B_j)
  • 所有输入均为整数

样例解释 1

高桥君可以按如下方式建设交通设施：

  • 支付费用 X1=1X_1=1，在岛屿 11 上建造机场。
  • 支付费用 X3=4X_3=4，在岛屿 33 上建造机场。
  • 支付费用 Y2=2Y_2=2，在岛屿 22 上建造港口。
  • 支付费用 Y4=3Y_4=3，在岛屿 44 上建造港口。
  • 支付费用 Z2=6Z_2=6，在岛屿 11 和岛屿 44 之间建造道路。

此时目标已经达成，总费用为 1616。不存在费用不超过 1515 的达成目标的方法，因此输出 1616。

样例解释 2

可以有机场、港口、道路三者之一未被建设的情况。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页