AT_past201912_l グラデーション

[problemUrl]: https://atcoder.jp/contests/past201912-open/tasks/past201912_l 二次元座標平面上に、$ 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 $ 倍である。(塔の大小は建設コストに関係しない。また、橋の交差は考慮しない。) 目的の達成に必要な最小の合計コストを求めよ。

入力は以下の形式で標準入力から与えられる。 > $ 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} $ 以下であれば正解と判定される。

### 注意 この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 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 $ - 入力中の値はすべて整数である。 ### Sample Explanation 1 $ 1 $ 番目の大きな塔と $ 2 $ 番目の大きな塔、$ 1 $ 番目の大きな塔と $ 3 $ 番目の大きな塔をそれぞれ直接結ぶべきである。合計コストは $ 1\ +\ 1\ =\ 2 $ となる。 ### Sample Explanation 2 小さな塔をそれぞれの大きな塔と結ぶべきである。合計コストは $ 10\ +\ 10\ \times\ 10\ +\ 10\ \times\ 10\ =\ 210 $ となる。