只能过样例和第一个测试点,玄关
查看原帖
只能过样例和第一个测试点,玄关
1140002
ppi_SAMA楼主2024/12/15 16:04
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, m;
int x[N], y[N];
struct node {
	int nxt, to;
	double dis;
} edge[N * 2];
int head[N], cnt;
int Pow(int a) {
	return a * a;
}
double diss(int a, int b) {
	int xx1 = x[a], yy1 = y[a], xx2 = x[b], yy2 = y[b];
	return sqrt(Pow(xx1 - xx2) + Pow(yy1 - yy2));
}
void add(int from, int to, double dis) {
	cnt++;
	edge[cnt].to = to;
	edge[cnt].nxt = head[from];
	edge[cnt].dis = dis;
	head[from] = cnt;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			add(i, j, diss(i, j));
		}
	}
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y, 0.0);//o.o
	}
	priority_queue<pair<double, int > >q;
	q.push(make_pair(0, 1));
	int tot = 0;
	double MST = 0;
	int vis[N] = {0};
	while (q.size() && tot < n) {
		double dis = q.top().first;
		int now = q.top().second;
		q.pop();
		if (vis[now]) continue;
		vis[now] = 1;
		MST += dis;
		tot++;
		for (int i = head[now]; i ; i = edge[i].nxt)
			if (!vis[edge[i].to])
				q.push(make_pair(-edge[i].dis, edge[i].to));
	}
	printf("%.2lf", -MST);
	return 0;
}
2024/12/15 16:04
加载中...