// // 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")