Алгоритм Прима

import heapq

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
used = [0] * n
Q = []
D = [10**18] * n
G = []
e = 0

D[0] = 0
heapq.heappush(Q, (0, 0, 0))

while Q and e < n:
    w, a, b = heapq.heappop(Q)
    if used[b]:
        continue
    used[b] = 1
    e += 1
    G.append([a, b, w])
    for i in range(n):
        if not used[i]:
            weight = ((A[b][0] - A[i][0])**2 + (A[b][1] - A[i][1])**2)**0.5
            if weight < D[i]:
                D[i] = weight
                heapq.heappush(Q, (weight, b, i))

z = 0
for a, b, w in G:
    z += w
print(z)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<pair<double, double>> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i].first >> A[i].second;
    }
    
    vector<int> used(n, 0);
    priority_queue<tuple<double, int, int>,
                   vector<tuple<double, int, int>>,
                   greater<tuple<double, int, int>>> Q;
    vector<double> D(n, 1e18);
    vector<tuple<int, int, double>> G;
    int e = 0;
    
    D[0] = 0;
    Q.push({0, 0, 0});
    
    while (!Q.empty() && e < n) {
        auto [w, a, b] = Q.top();
        Q.pop();
        if (used[b]) continue;
        used[b] = 1;
        e++;
        G.push_back({a, b, w});
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                double dx = A[b].first - A[i].first;
                double dy = A[b].second - A[i].second;
                double weight = sqrt(dx*dx + dy*dy);
                if (weight < D[i]) {
                    D[i] = weight;
                    Q.push({weight, b, i});
                }
            }
        }
    }
    
    double z = 0;
    for (auto [a, b, w] : G) {
        z += w;
    }
    cout << fixed << setprecision(10) << z << endl;
    
    return 0;
}