← 返回题目列表

Codeforces · 1245/D

D. 七九寺与电网

中文机器翻译题面 查看原题

七九寺是南黑螺寺的新住神。她的第一份工作是这样的:

X 县有 $$$n$$$ 个新城市。城市编号从 $$$1$$$ 到 $$$n$$$。城市$$$i$$$位于神社以北$$$x_i$$$公里和神社以东$$$y_i$$$公里。即使$$$i \ne j$$$ 也有可能$$$(x_i, y_i) = (x_j, y_j)$$$。

七九寺必须为每个城市提供电力,方法是在该城市建立一个发电站,或者在该城市与另一个已经通电的城市之间建立连接。因此,如果该城市内有发电站,或者通过直接连接或通过连接链连接到有电力的城市,则该城市就有电力。

- 在城市 $$$i$$$ 建造一座发电站将花费 $$$c_i$$$ 日元;
- 在 $$$i$$$ 城市和 $$$j$$$ 城市之间建立连接每公里连接线将花费 $$$k_i + k_j$$$ 日元。然而,电线只能沿着基本方向(北、南、东、西)。电线可以相互交叉。每条电线的两个端点都必须位于某些城市。如果城市 $$$i$$$ 和城市 $$$j$$$ 通过电线连接,则该电线将经过从城市 $$$i$$$ 到城市 $$$j$$$ 的任何最短路径。因此,如果 City $$$i$$$ 和 City $$$j$$$ 连接,电线的长度为 $$$|x_i - x_j| + |y_i - y_j|$$$ 公里。

七九寺希望花尽可能少的钱来做这份工作,因为据她说,世界上除了钱之外什么都没有。然而,她在五年级时就去世了,所以她不够聪明,无法做到这一点。因此,新的驻地神请求你的帮助。

因此,您必须向七九寺提供以下信息:向所有城市提供电力所需的最低日元金额、将在哪些城市建设发电站以及要建立的连接。

如果有多种方式选择城市和连接以获得最低建造价格,则打印其中任何一种。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$) — 城市数量。

然后是 $$$n$$$ 行。第 $$$i$$$ 行包含两个以空格分隔的整数 $$$x_i$$$ ($$$1 \leq x_i \leq 10^6$$$) 和 $$$y_i$$$ ($$$1 \leq y_i \leq 10^6$$$) — 第 $$$i$$$ 城市的坐标。

下一行包含 $$$n$$$ 以空格分隔的整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$) — 在第 $$$i$$$ 个城市建造发电站的成本。

最后一行包含 $$$n$$$ 空格分隔的整数 $$$k_1, k_2, \dots, k_n$$$ ($$$1 \leq k_i \leq 10^9$$$)。

输出

在第一行打印一个整数,表示所需的最低日元金额。

然后,打印一个整数 $$$v$$$ — 待建发电站的数量。

接下来,打印 $$$v$$$ 以空格分隔的整数,表示将建设电站的城市的索引。每个数字应从 $$$1$$$ 到 $$$n$$$ 且所有数字应成对不同。您可以按任意顺序打印数字。

之后,打印一个整数 $$$e$$$ — 要建立的连接数。

最后,打印 $$$e$$$ 整数对 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \ne b$$$),表示将在 City $$$a$$$ 和 City $$$b$$$ 之间建立连接。每个无序城市对最多应包含一次(对于每个 $$$(a, b)$$$ 不应再有 $$$(a, b)$$$ 或 $$$(b, a)$$$ 对)。您可以按任意顺序打印这些对。

如果有多种方式选择城市和连接以获得最低建造价格,则打印其中任何一种。

示例

输入 #1

3
2 3
1 1
3 2
3 2 3
3 2 3

输出 #1

8
3
1 2 3 
0

输入 #2

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

输出 #2

27
1
2 
2
1 2
2 3

注意

样本中给出的答案请参考下图(有电站的城市为绿色,其他城市为蓝色,电线为红色):

对于第一个示例,在所有城市建设发电站的成本为 $$$3 + 2 + 3 = 8$$$。可以看出,没有任何配置的成本低于8日元。

对于第二个示例,在城市 2 建造电站的成本为 2。连接城市 1 和城市 2 的成本为 $$$2 \cdot (3 + 2) = 10$$$。连接城市 2 和城市 3 的成本为 $$$3 \cdot (2 + 3) = 15$$$。因此,总成本为 $$$2 + 10 + 15 = 27$$$。可以看出,没有任何配置的成本低于27日元。