gistfile1.cpp

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

struct Node{
	int x;
	int y;

	Node *component;
	vector<Node*> *children;

	Node(int x, int y): x(x), y(y), component(this), children(new vector<Node*>(1, this)) {}

	void update(){
		for(size_t i = 0; i < children->size(); i++){
			children->at(i)->component = component;
			children->at(i)->children = children;
			// if (children->at(i)->component != component)
			// 	children->at(i)->update();
		}
	}
};

struct Edge
{
	double weight ;
	Node *from;
	Node *to;

	Edge (double weight): weight(weight) {}

	bool operator<(Edge const& rhs) const {
	    return weight < rhs.weight;
	}
};


int main () {
	int number_of_inst = 0;
	size_t number_of_cities = 0;
	int maximal_line_length = 0;
	int k_x = 0;
	int k_y = 0;
	cin>>number_of_inst;
	vector<int>outputs(0,0);

	for (int i= 0; i< number_of_inst; i++){
		double MST_weight = 0;

		cin >> number_of_cities;
		cin >> maximal_line_length;

		vector<Node*> node_queue;
		queue<Edge> edge_queue_sorted;
		vector<Edge> edge_queue;

		for (size_t j = 0; j < number_of_cities; j++){
			cin >> k_x;
			cin >> k_y;

			Node *temp_node1 = new Node(k_x, k_y);

			size_t cycler = node_queue.size();
			for (size_t k = 0; k < cycler; k++){
				Node *temp_node2 = node_queue[k];
				double distance = sqrt((double) ((temp_node2->x) - k_x)*((temp_node2->x) - k_x) + ((double)((temp_node2->y) - k_y))*((temp_node2->y)- k_y));
				if(distance < 0) {
				    cout << "oops";
				}
				if (distance <= maximal_line_length){
					Edge edgy = Edge(distance);
					edgy.from = temp_node1;
					edgy.to = temp_node2;
					edge_queue.push_back(edgy);
				}
			}
			node_queue.push_back(temp_node1);
		}
		sort(edge_queue.begin(), edge_queue.end());

		for (size_t z = 0; z < edge_queue.size(); z++){
			edge_queue_sorted.push(edge_queue[z]);
		}

		while (!edge_queue_sorted.empty()){
			Edge e = edge_queue_sorted.front();

			if (e.from->component != e.to->component) {
				MST_weight += e.weight;

			    if (e.from->children->size() >= e.to->children->size()){
				    for (size_t i = 0; i < e.to->children->size(); i++) {
				        e.from->children->push_back(e.to->children->at(i));
				    }
				    e.from->update();
			    }
			    else {
				    for (size_t i = 0; i < e.from->children->size(); i++) {
				        e.to->children->push_back(e.from->children->at(i));
				    }
				    e.to->update();
			    }
			}
			edge_queue_sorted.pop();
		}
		Node *example_node = node_queue.front();
		if (example_node->children->size() == number_of_cities)
			outputs.push_back(static_cast<int>(MST_weight));
		else
			outputs.push_back(-1);
	}
	
	for(size_t i = 0; i < outputs.size(); i ++){
		cout<<outputs[i]<<endl;
	}
	
    return 0;
}