def solve(N, M, LARGE, SMALL): from math import sqrt edges = [] for i in range(N): x1, y1, c1 = LARGE[i] for j in range(i + 1, N): x2, y2, c2 = LARGE[j] d = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) if c1 != c2: d *= 10 edges.append((d, i, j)) large_edges = edges[:] INF = 9223372036854775807 ret = INF for subset in range(2 ** M): edges = large_edges[:] for m in range(M): if subset & (1 << m): x2, y2, c2 = SMALL[m] for i in range(N): x1, y1, c1 = LARGE[i] d = sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) if c1 != c2: d *= 10 edges.append((d, i, N + m)) init_unionfind(N + M) edges.sort() cost = 0 for d, i, j in edges: if is_connected(i, j): continue unite(i, j) cost += d ret = min(ret, cost) return ret