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

struct DSU {
    vector<int> f;

    DSU(int n) {
        f.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) f[i] = i;
    }

    int rt(int u) {
        if (u == f[u]) return u;
        return f[u] = rt(f[u]);
    }

    int same(int u, int v) {
        return rt(u) == rt(v);
    }

    void merge(int u, int v) {
        f[rt(u)] = rt(v);
    }
};
void solve() {
    int n, c;
    cin >> n >> c;

    vector<array<int, 3>> e;

    vector<int> x(n + 1), y(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        for (int j = 1; j < i; j++) {
            int w = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
            if (w >= c) {
                e.push_back({w, i, j});
            }
        }
    }

    sort(e.begin(), e.end());
    DSU dsu(n);
    int sum = 0, cnt = 0;
    for (auto [w, u, v] : e) {
        if (dsu.same(u, v)) continue;
        dsu.merge(u, v);
        sum += w;
        cnt++;
    }
    if (cnt == n - 1) {
        cout << sum << '\n';
    } else {
        cout << "-1\n";
    }
}
signed main() {
    int t = 1;
    // cin >> t;
    while (t--) solve();
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/

0 条评论

目前还没有评论...

信息

ID
489
时间
ms
内存
MiB
难度
3
标签
递交数
178
已通过
44
上传者