글 읽기 - 9%에서 틀렸다고 나옵니다.

kj9203 6년 전 0

어디가 틀린지 감도 안오네요.. 맞게 한거같은데..

#include <iostream>
#include <vector>
#include <cmath>
#include <tuple>
#include <algorithm>
using namespace std;
int uf[1004];
int N, M;
int find(int a) {
	if (uf[a] == a) return a;
	return uf[a] = find(uf[a]);
}

bool merge(int a, int b) {
	if (a == b) return false;
	uf[a] = b;
	return true;
}
double dist(int x1, int x2, int y1, int y2) {
	return sqrt(abs(x1 - x2)*abs(x1 - x2) + abs(y1 - y2)*abs(y1 - y2));
}
bool comp(tuple<int, int, double> a, tuple<int, int, double> b) {
	return get<2>(a) < get<2>(b);
}
vector<tuple<int, int, double>> e;
int x[1004], y[1004];
int main() {
	int cnt = 0;
	cin >> N >> M;
	for (int i = 1; i <=N; i++) {
		cin >> x[i] >> y[i];
		uf[i] = i;
	}

	for (int j = 1; j <=M; j++) {
		int a, b;
		cin >> a >> b;
		int aa = find(a), bb = find(b);
		if (merge(aa, bb)) cnt++;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			e.push_back(tuple<int, int, double>(i, j, dist(x[i], x[j], y[i], y[j])));
		}
	}
	sort(e.begin(), e.end(), comp);

	double result = 0;
	bool com = false;
	if (cnt >= N - 1) com = true;
	int root = find(1);
	if (!com) {
		for (int i = 0; ; i++) {
			int a = find(get<0>(e[i])), b = find(get<1>(e[i]));
			if (merge(a,b)) {
				result += get<2>(e[i]);
				if (++cnt == N - 1) break;
			}
		}
	}
	printf("%.2lf\n", result);

}