发电站(Power Stations)

题目描述

小 Z 作为某工厂的工程师，要对这个工厂里的共 $n$ 个设备通上电，刚开始这些设备都没有通上电。具体地，这些设备编号为 $1,2,\cdots,n$，并且工厂可以看成是平面直角坐标系，设备 $i$ 的坐标为 $(x_i,y_i)$。

小 Z 想要对每一个设备都通上电，第 $i$ 个设备能通上电，当且仅当满足以下两个条件中的任意一个：

1. 为第 $i$ 个设备建造一个火力发电站，这将花费 $c_i$ 元
2. 选择另一个有电的设备 $j(j\ne i)$，在设备 $i$ 和设备 $j$ 之间接一根电线，安装电线的价格是每公里 $k_i+k_j$ 元，其中 $k_i,k_j$ 分别是设备 $i$ 和设备 $j$ 的用电量。电线只能走基本方向（东、南、西、北），电线可以互相交叉但互不影响。换句话说，如果在 $i$ 和 $j$ 之间拉一根电线，那么电线的长度会是曼哈顿距离 $|x_i-x_j|+|y_i-y_j|$，因此，拉电线的费用为 $(k_i+k_j)(x_i-x_j|+|y_i-y_j|)$ 元。

问，小 Z 让每个设备都通上电所需的最小花费是多少。

「注意」

• 有可能出现，$i\ne j$，但是 $(x_i,y_i)=(x_j,y_j)$，即同一个点可能有两个设备。
• 初始，这些设备都没有通电，也没有火力发电站。

输入格式

第一行有一个整数 $id(1\leq id \leq 20)$，表示测试点编号。你可以用这个信息来判断每个测试点的特殊性质（具体见数据范围与约定）。

第二行有一个整数$n$，表示设备数量。

接下来有 $n$ 行，第 $i+2$ 行有两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个设备的坐标。

紧接着一行有 $n$ 个整数，分别是 $c_1,c_2,\cdots,c_n$，表示在 $i$ 设备建造火力发电站的费用。

最后一行 $n$ 个整数，分别是 $k_1,k_2,\cdots,k_n$，表示每个设备的发电量。

输出格式

输出一个整数，表示让所有设备通上电的最小花费。

样例输入 #1

1
5
1 2
1 93
1 9
1 38
1 8
485167613 784430249 637393481 271981451 436803228
1 1 1 1 1

样例输出 #1

271981633

样例输入 #2

20
3
2 1
1 2
3 3
23 2 23
3 2 3

样例输出 #2

27

数据范围

样例 1 解释：

在第 $4$ 个设备建设发电站，其他 $4$ 个设备通过电线连向第 $4$ 个设备。

样例 2 解释：

在第 $2$ 个设备建设发电站，另外两个设备通过电线连向第 $2$ 个设备，总花费是 $2+10+15=27$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接