The Quantum Entanglement Network
Scientists are building a quantum communication network connecting n particles. Each particle has a spin value (0 or 1).
To establish a quantum link between two particles, the energy cost equals the distance between them. However, a link can only be formed between particles with different spin values (0 and 1).
Find the minimum total energy required to connect all particles into a single network where every particle can communicate with every other particle (directly or indirectly).
If it's impossible to connect all particles, return -1.
Input Format
The first line contains an integer n, the number of particles. The next n lines each contain three integers: x, y (coordinates), and spin (0 or 1). Distance between two particles is |x1-x2| + |y1-y2| (Manhattan distance).
Output Format
Print the minimum total energy, or -1 if impossible.
Examples
Example 1
Example 2
Constraints
•
2 ≤ n ≤ 1000
•
0 ≤ x, y ≤ 10^6
•
spin is 0 or 1
Code
Case 1
Case 2