백준 10021번 Watering the Fields

문제

Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000).

Each field i is described by a distinct point (xi, yi) in the 2D plane, with 0 <= xi, yi <= 1000. The cost of building a water pipe between two fields i and j is equal to the squared Euclidean distance between them:

(xi - xj)^2 + (yi - yj)^2

FJ would like to build a minimum-cost system of pipes so that all of his fields are linked together -- so that water in any field can follow a sequence of pipes to reach any other field.

Unfortunately, the contractor who is helping FJ install his irrigation system refuses to install any pipe unless its cost (squared Euclidean length) is at least C (1 <= C <= 1,000,000).

Please help FJ compute the minimum amount he will need pay to connect all his fields with a network of pipes.

입력

• Line 1: The integers N and C.
• Lines 2..1+N: Line i+1 contains the integers xi and yi.

출력

• Line 1: The minimum cost of a network of pipes connecting the fields, or -1 if no such network can be built.

 

 

parent 업데이트 과정에서 그 길이를 단축시키는 로직 추가안하면 시간초과 발생함.

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;


int N, C;
pair<int, int> node[2000];
int parent[2000];


struct Node
{
	int start;
	int end;
	int dist;
};

bool compare(Node n1, Node n2)
{
	return n1.dist < n2.dist;
}

vector<Node> vec;


int findParent(int node)
{
	if (node == parent[node])
	{
		return node;
	}
	return parent[node] = findParent(parent[node]);
}




int main(int argc, char** argv)
{
	cin >> N >> C;
	for (int i = 0; i < N; i++)
	{
		int x, y;
		cin >> x >> y;
		node[i] = { x,y };
	}

	for (int i = 0; i < N; i++)
	{
		parent[i] = i;
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			int x1 = node[i].first;
			int y1 = node[i].second;
			int x2 = node[j].first;
			int y2 = node[j].second;

			int cost = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
			if (cost >= C)
			{
				vec.push_back({ i,j,cost });
			}
		}
	}
	
	sort(vec.begin(), vec.end(), compare);
	int res = 0;
	int cont = 0;
	for (int i = 0; i < vec.size(); i++)
	{
		int start = vec[i].start;
		int end = vec[i].end;
		int dis = vec[i].dist;

		int node1 = findParent(start);
		int node2 = findParent(end);
		if (node1 != node2)
		{
			cont++;
			parent[node2] = node1;
			res += dis;
		}
	}
	if (cont != N - 1)
	{
		cout << -1 << endl;
		return 0;
	}

	cout << res << endl;


	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}