初音未来 • 8天前
using namespace std;
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;
}
评论:
请先登录,才能进行评论