让DS受到一点信竞的震撼吧w

题目：

完整版

始皇修路

题目背景

昔者秦王并吞六国，混一寰宇，书同文，车同轨。思欲通达四海，固江山之基，乃命内史腾监造驰道。

大秦版图，纵横万里，其间沃野、崇山、大泽交错。王命：择关中、齐鲁、燕赵、荆楚、吴越等要冲之地，共计 K 处，定为“枢纽”。

承命大臣需于大地网格之上，筑路以联此 K 处。然国库虽丰，亦不欲徒耗民力。凡筑路者，必循经纬之线，或南北，或东西。

每历一格，耗金若干。且山川险易不同，某些地域有巨石险滩，不可逾越；某些地域则已有前朝废弃古道，修复之耗极微。

内史腾欲求一策，使此 K 处枢纽尽皆连通，且总耗金最少。若不能连通，则大秦威严受损，必究其责。

尔等工部后进，能以此算筹之术，定此锦绣山河之枢纽乎？

题目描述

在大秦帝国的广袤国土上，你需要设计一个最优的交通网络。国土被抽象为一个巨大的坐标平面。

给定 K 个必须连通的枢纽城市，每个城市的坐标为 (x_i, y_i)。

道路只能沿水平或垂直方向修建（曼哈顿距离）。由于地理环境的差异，在某些特定的网格区域（矩形区域）修建道路的单位长度成本不同。

你的目标是找到一种方案，使得所有 K 个城市连通，且总修建成本最低。

输入格式

第一行包含一个整数 K，表示枢纽城市的数量。

接下来的 K 行，每行包含两个整数 x_i, y_i，表示枢纽城市的坐标。

下一行包含一个整数 M，表示具有特殊成本的矩形区域数量。

接下来的 M 行，每行包含 x_{1}, y_{1}, x_{2}, y_{2}, c，表示在左下角 (x_1, y_1) 到右上角 (x_2, y_2) 的矩形区域内（含边界），单位道路修建成本为 c。

默认的全球单位道路成本为 $C_{default}$（在输入中给定）。

输出格式

一行一个整数$P$，代表最小的修建成本

输入输出样例 #1

输入 #1```
3
1 1
2 2
3 3
0
1
``输出 #1``
4
```说明/提示

样例$1$说明：

$3$个枢纽在 $$ (1,1), (2,2), (3,3) $$ ，无特殊区域，默认单位成本为 1。

最优方案是连接 $$ (1,1) - (2,1) - (2,2) - (3,2) - (3,3) $$ ，总长度 4

测试点编号 |
K (枢纽数) |
M (特殊区域) |
坐标范围 |

1 - 3 |
\le 5 |
0 |
\le 1000 |

4 - 6 |
\le 8 |
\le 10 |
\le 10^5 |

7 - 11 |
\le 10 |
\le 50 |
\le 10^9 |

12 - 16 |
\le 12 |
\le 100 |
\le 10^9 |

保证$$0 \le P \le 2^{128}$$

重合特殊成本区域的成本以更小的计

太长不看版：

用最小的代价连通K个枢纽节点（？）

提示词选用claude code内置提示词，一次出

对照组：cc+Minimax-M3（官）

首字4s，103tps，共耗时318.3s

结果：

Gemini-3.1-Pro extended（网页哈基米）

结果：

正片开始

Deepseek-v4-pro-GA 官

首字8s，57tps，耗时1226s，0.69￥，0.5mtok，缓存0.36mtok

结果

Deepseek-v4-flash-GA 官

首字3.7s，51tps，耗时1332.2s，1.76￥，4.48mtok，4m缓存

结果

话说这个题目佬友们们觉得难度如何w……

有佬友想出正解吗w？