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

AT_kupc2020_f.GRIDMST

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

有一个顶点按 HH 行 WW 列排列的网格图。

从上往下第 ii 行，从左往右第 jj 列的顶点记作 (i,j)(i, j)，其中 1≤i≤H, 1≤j≤W1 \leq i \leq H,\ 1 \leq j \leq W。

有四个广义单调不减的正整数序列 A,B,C,DA, B, C, D，它们的长度分别为 H−1,W,H,W−1H-1, W, H, W-1。

顶点 (i,j)(i, j) 与顶点 (i+1,j)(i+1, j) 之间有一条无向边，权值为 Ai+BjA_i + B_j，其中 1≤i≤H−1, 1≤j≤W1 \leq i \leq H-1,\ 1 \leq j \leq W。

顶点 (i,j)(i, j) 与顶点 (i,j+1)(i, j+1) 之间有一条无向边，权值为 Ci+DjC_i + D_j，其中 1≤i≤H, 1≤j≤W−11 \leq i \leq H,\ 1 \leq j \leq W-1。

除此之外没有其他边。

请计算该图的最小生成树所包含的边权之和。

输入格式

输入通过标准输入给出，格式如下：

HH WW A1A_1 A2A_2 …\ldots AH−1A_{H-1} B1B_1 B2B_2 …\ldots BWB_W C1C_1 C2C_2 …\ldots CHC_H D1D_1 D2D_2 …\ldots DW−1D_{W-1}

输出格式

输出该网格图的最小生成树所包含的边权之和。

注意，答案可能超出 32 位整数范围。

输入输出样例

  • 输入#1

    2 3
1
1 3 6
1 4
1 2

    输出#1

    17

  • 输入#2

    4 3
1 13 15
3 6 11
3 6 6 11
9 17

    输出#2

    173

说明/提示

限制条件

  • 2≤H≤1052 \leq H \leq 10^5
  • 2≤W≤1052 \leq W \leq 10^5
  • 1≤Ai≤106 (1≤i≤H−1)1 \leq A_i \leq 10^6\ (1 \leq i \leq H-1)
  • 1≤Bj≤106 (1≤j≤W)1 \leq B_j \leq 10^6\ (1 \leq j \leq W)
  • 1≤Ci≤106 (1≤i≤H)1 \leq C_i \leq 10^6\ (1 \leq i \leq H)
  • 1≤Dj≤106 (1≤j≤W−1)1 \leq D_j \leq 10^6\ (1 \leq j \leq W-1)
  • Ai≤Ai+1 (1≤i≤H−2)A_i \leq A_{i+1}\ (1 \leq i \leq H-2)
  • Bj≤Bj+1 (1≤j≤W−1)B_j \leq B_{j+1}\ (1 \leq j \leq W-1)
  • Ci≤Ci+1 (1≤i≤H−1)C_i \leq C_{i+1}\ (1 \leq i \leq H-1)
  • Dj≤Dj+1 (1≤j≤W−2)D_j \leq D_{j+1}\ (1 \leq j \leq W-2)

样例解释 1

给定的图如上图所示。该图的最小生成树所包含的边权之和为 1717。

由 ChatGPT 4.1 翻译

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

首页