题目详情题解（0）讨论（0）提交记录（0）

AT_past201912_l.グラデーション

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

平面直角坐标系上有 nn 个普通点和 mm 个特殊点。第 ii 个普通点的坐标为 (xi,yi)(x_i,y_i)，颜色为 cic_i；第 ii 个特殊点的坐标为 (pi,qi)(p_i,q_i)，颜色为 oio_i。同一个坐标上可能有多个点。

你想用线段连接一些点，使得任意两个普通点之间都可以通过在线段上移动到达。画一条新线段的成本在线段两端点同色时为线段长度，异色时为线段长度的 1010 倍。（在此，我们不考虑相交的线段。）

输出达成目标的最小总成本。

输入格式

第一行输入两个整数 nn 和 mm。

接下来 nn 行，每行三个整数 xi,yi,cix_i,y_i,c_i。

接下来 mm 行，每行三个整数 pi,qi,oip_i,q_i,o_i。

输出格式

输出一行一个实数，最小总成本。你的答案与标准答案的误差不超过 10−610^{-6} 即可被判定为通过。

数据规模与约定

2≤n≤302 \le n \le 30，1≤m≤51 \le m \le 5，0≤xi,yi,pi,qi≤10000 \le x_i,y_i,p_i,q_i \le 1000，1≤ci,oi≤31 \le c_i,o_i \le 3。（1,2,31,2,3 分别表示红、绿、蓝三色）

输入输出样例

  • 输入#1

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

    输出#1

    2.000000000000

  • 输入#2

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

    输出#2

    210.000000000000

输入解题思路，AI测评打分。不知道怎么写?

首页