AT_kupc2020_f GRIDMST

有一个顶点按 $H$ 行 $W$ 列排列的网格图。 从上往下第 $i$ 行，从左往右第 $j$ 列的顶点记作 $(i, j)$，其中 $1 \leq i \leq H,\ 1 \leq j \leq W$。 有四个**广义单调不减**的正整数序列 $A, B, C, D$，它们的长度分别为 $H-1, W, H, W-1$。 顶点 $(i, j)$ 与顶点 $(i+1, j)$ 之间有一条无向边，权值为 $A_i + B_j$，其中 $1 \leq i \leq H-1,\ 1 \leq j \leq W$。 顶点 $(i, j)$ 与顶点 $(i, j+1)$ 之间有一条无向边，权值为 $C_i + D_j$，其中 $1 \leq i \leq H,\ 1 \leq j \leq W-1$。 除此之外没有其他边。 请计算该图的最小生成树所包含的边权之和。

输入通过标准输入给出，格式如下： > $H$ $W$ $A_1$ $A_2$ $\ldots$ $A_{H-1}$ $B_1$ $B_2$ $\ldots$ $B_W$ $C_1$ $C_2$ $\ldots$ $C_H$ $D_1$ $D_2$ $\ldots$ $D_{W-1}$

输出该网格图的最小生成树所包含的边权之和。 注意，答案可能超出 32 位整数范围。

## 限制条件 - $2 \leq H \leq 10^5$ - $2 \leq W \leq 10^5$ - $1 \leq A_i \leq 10^6\ (1 \leq i \leq H-1)$ - $1 \leq B_j \leq 10^6\ (1 \leq j \leq W)$ - $1 \leq C_i \leq 10^6\ (1 \leq i \leq H)$ - $1 \leq D_j \leq 10^6\ (1 \leq j \leq W-1)$ - $A_i \leq A_{i+1}\ (1 \leq i \leq H-2)$ - $B_j \leq B_{j+1}\ (1 \leq j \leq W-1)$ - $C_i \leq C_{i+1}\ (1 \leq i \leq H-1)$ - $D_j \leq D_{j+1}\ (1 \leq j \leq W-2)$ ## 样例解释 1  给定的图如上图所示。该图的最小生成树所包含的边权之和为 $17$。 由 ChatGPT 4.1 翻译