题解 | #Freckles#

//
// Created by lenovo on 2023/8/12.
//
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

const int MAXN = 1000, INF = 0x3f3f3f3f; //定义一个INF表示无穷大。
int n; //图的边数
double g[MAXN][MAXN], dist[MAXN], res;
//我们用g[][]数组存储这个图，dist[]储存到集合S的距离，res保存结果。
bool book[MAXN];//用book数组记录某个点是否加入到集合S中。

double getlen(double x1, double x2, double y1, double y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

void prim() {
    dist[1] = 0;
    book[1] = true;
    for (int i = 2; i <= n; i++) // dist[i]在最开始的时候是最大值INF
        dist[i] = min(dist[i], g[1][i]);
    for (int i = 2; i <= n; i++) {
        double tmp = INF;
        int t = -1;
        for (int j = 2; j <= n; j++) {
            if (!book[j] && dist[j] < tmp) {
                tmp =  dist[j];
                t = j;
            }
        }
        if (t == -1) {
            res = INF;
            return;
        }
        book[t] = true;
        res += dist[t];
        for (int j = 2; j <= n; j++)
            dist[j] = min(dist[j], g[t][j]);
    }
}


int main() {
    // 边的数目
    while (cin >> n) {
        vector<pair<double, double>> pos(n);
        for (int i = 0; i < n; i++)
            cin >> pos[i].first >> pos[i].second;
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1; j <= n ; j++) {
                g[i][j] = INF;//初始化任意两个点之间的距离为正无穷（表示这两个点之间没有边）
            }
            dist[i] = INF;//初始化所有点到集合S的距离都是正无穷
        }
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                double distance = getlen(pos[i].first, pos[j].first, pos[i].second,
                                         pos[j].second);
                g[i + 1][j + 1] = g[j + 1][i + 1] = distance;
            }
        }
        prim();
        printf("%.2f\n", res);
    }
}
// 64 位输出请用 printf("%lld")

// 64 位输出请用 printf("%lld")