/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
注意
この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
二次元座標平面上に、N 本の大きな塔と M 本の小さな塔が建っている。i 本目の大きな塔 (1 \leqq i \leqq N) の座標は (x_i, y_i)、色は c_i であり、i 本目の小さな塔 (1 \leqq i \leqq M) の座標は (X_i, Y_i)、色は C_i である。ここで、塔の色は整数として与えられ、1, 2, 3 がそれぞれ赤、緑、青を表す。なお、同一の座標に複数の塔が存在する可能性がある。
あなたは、二本の塔を結ぶ橋を何本か建設して、どの大きな塔から別のどの大きな塔へも何本かの橋を渡って到達できるようにしたい。(小さい塔はどのように扱ってもよい。)
同じ色の塔を結ぶ橋の建設コストは二本の塔の間のユークリッド距離に等しく、異なる色の塔を結ぶ橋の建設コストはその 10 倍である。(塔の大小は建設コストに関係しない。また、橋の交差は考慮しない。)
目的の達成に必要な最小の合計コストを求めよ。
制約
- 2 \leqq N \leqq 30
- 1 \leqq M \leqq 5
- 0 \leqq x_i, y_i \leqq 1,000
- 0 \leqq X_i, Y_i \leqq 1,000
- 1 \leqq c_i, C_i \leqq 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 番目の大きな塔と 2 番目の大きな塔、1 番目の大きな塔と 3 番目の大きな塔をそれぞれ直接結ぶべきである。合計コストは 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 となる。
Warning
Do not make any mention of this problem until December 29, 2019, 05:00 a.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
There are N large towers and M small towers built on a two-dimensional coordinate plane. The i-th large tower (1 \leq i \leq N) has the coordinate (x_i, y_i) and the color c_i, and the i-th small tower (1 \leq i \leq N) has the coordinate (X_i, Y_i) and the color C_i. Here, the color of a tower is given as an integer, where 1, 2, 3 stand for red, green, blue, respectively. There may be multiple towers at the same coordinates.
You want to construct some bridges connecting two towers so that any large tower can be reached from any other large tower using some number of bridges. (The small towers can be treated in any way you like.)
The cost needed to construct a bridge connecting two towers is equal to the Euclidean distance between them, multiplied by 10 if the colors of the towers are different. (The cost does not depend on the sizes of the towers. Also, we do not consider the crossing of bridges.)
Find the minimum total cost needed to achieve your objective.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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
Output
Print a real number representing the minimum total cost needed to achieve the objective. Your output is considered correct if the absolute or relative error from the judge's output is at most 10^{-6}.
Sample Input 1
3 1 0 0 1 0 1 1 1 0 1 1 1 1
Sample Output 1
2.000000000000
We should directly connect the first and second large towers, then the first and third large towers, for a total cost of 1 + 1 = 2.
Sample Input 2
3 1 0 10 1 10 0 2 10 20 3 10 10 1
Sample Output 2
210.000000000000
We should connect the small tower to each of the large towers, for a total cost of 10 + 10 \times 10 + 10 \times 10 = 210.