← 返回题目列表

AtCoder · past201912_l

L. 渐变

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

警告

在日本标准时间 2019 年 12 月 29 日凌晨 05:00 之前请勿提及此问题。如有违反,可要求赔偿。

考试结束后,您可以向其他人透露您的总分和等级,但仅此而已(例如,您解决了哪些问题)。

问题陈述

有 N 大型塔楼和 M 建立在二维坐标平面上的小塔。的 i-第一个大塔 (1 \leq i \leq N) 有坐标 (x_i, y_i) 和颜色 c_i,以及 i第一个小塔 (1 \leq i \leq N) 有坐标 (X_i, Y_i) 和颜色 C_i。这里,塔的颜色以整数给出,其中 1, 2, 3 分别代表红、绿、蓝。同一坐标处可能有多个塔。

您想要建造一些连接两个塔的桥梁,以便使用一定数量的桥梁可以从任何其他大型塔到达任何大型塔。 (小塔可以按照您喜欢的方式进行处理。)

建造一座连接两座塔的桥梁所需的成本等于它们之间的欧几里德距离乘以 10 如果塔的颜色不同。 (费用与塔的大小无关。而且,我们不考虑过桥的情况。)

找出实现目标所需的最低总成本。

约束

  • 2 \leq N \leq 30
  • 1 \leq M \leq 5
  • 0 \leq x_i, y_i \leq 1000
  • 0 \leq X_i, Y_i \leq 1000
  • 1 \leq c_i, C_i \leq 3
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N
X_1 Y_1 C_1
X_2 Y_2 C_2
:
X_M Y_M C_M

输出

打印一个实数,代表实现目标所需的最低总成本。如果法官输出的绝对或相对误差最多为,则您的输出被认为是正确的 10^{-6}.


示例输入 1

3 1
0 0 1
0 1 1
1 0 1
1 1 1

示例输出 1

2.000000000000

我们应该直接连接第一和第二个大塔,然后连接第一和第三个大塔,总成本为 1 + 1 = 2.


示例输入 2

3 1
0 10 1
10 0 2
10 20 3
10 10 1

示例输出 2

210.000000000000

我们应该将小塔连接到每个大塔,总成本为 10 + 10 \times 10 + 10 \times 10 = 210.