SP7971 ACPC10I - The Cyber Traveling Salesman

由于地球人口急剧增长，计划在月球上建设多个城市。我们需要你帮助规划这些城市之间的最佳道路系统。鉴于在月球修建道路的费用较高，我们只需要一条从输入中第一个城市出发、经过所有其他城市恰好一次（顺序不限），然后返回起点城市的道路环路。（这实际上是旅行商问题的一个变种。） 你会得到每对城市之间修建道路的费用。尽管道路是单向的，但从城市 $i$ 到 $j$ 与从城市 $j$ 到 $i$ 的建造成本是相同的。当若干条道路在非城市位置交汇时，还需考虑修建绕行桥梁的费用。这笔费用计算方式是 $k \ast (k - 1) \ast C/2$，其中 $k$ 是该地点交汇的道路数量，$C$ 是给定的常数。请注意，所有城市的分布确保没有三个城市在一条直线上。

程序将接受一个或多个测试用例。每个测试用例由 $2 \ast N + 1$ 行组成： - 第一行包含两个整数：$N$（表示城市数量，$2 < N < 9$）和 $C$（用于计算桥梁费用的系数，$0 < C \leq 1,000,000$）。 - 接下来 $N$ 行表示城市的笛卡尔坐标，每行包含两个整数 $x_i$ 和 $y_i$，范围为 $-1,000 \leq x_i, y_i \leq 1,000$。每个城市都有独特的位置。 - 随后的 $N$ 行提供一个 $N \times N$ 的矩阵，表示城市间的道路建造费用，以行优先顺序提供。第 $i$ 行的第 $j$ 个值为 $c_{ij}$，表示从城市 $i$ 到城市 $j$ 的费用，其中 $0 < c_{ij} \leq 10^6$，并且 $c_{ij} = c_{ji}$， $c_{ii} = 0$。 测试数据以一行两个零结束。

对于每个测试用例，输出以下格式的行： `k. M` 其中 $k$ 是测试用例的编号（从1开始），$M$ 是修建整个道路系统所需的最低费用。 **本翻译由 AI 自动生成**