啊啊

初音未来  •  8天前


include <bits/stdc++.h>

using namespace std;

define INF 0x3f3f3f3f

bool vis[5050]; double dis[5050]; int a[5050][2]; int n;

double jl(int x1, int y1, int x2, int y2) {

return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2));

}

void prim(int v) {

for (int i = 1; i <= n; i++) {
	double d = jl(a[1][0], a[1][1], a[i][0], a[i][1]);
	dis[i] = d;
}
for (int i = 1; i <= n; i++) {
	double minn = INF;
	for (int j = 1; j <= n; j++) {
		if (vis[j] == 0 && dis[j] < minn) {
			minn = dis[j];
			v = j;
		}
	}
	vis[v] = 1;
	for (int j = 1; j <= n; j++) {
		double d = jl(a[v][0], a[v][1], a[j][0], a[j][1]);
		if (vis[j] == 0 && dis[j] > d) {
			dis[j] = d;
		}
	}
}

}

int main() {

cin >> n;
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++)
	cin >> a[i][0] >> a[i][1];
prim(1);
double ans = 0;
for (int i = 1; i <= n; i++) {
	ans += dis[i];
}
printf("%.2lf", ans);
return 0;

}


评论:

请先登录,才能进行评论