Road Network

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const int INF = 0x3f3f3f3f; //❄️
    5#define int long long
    6vector<int> parent;
    7struct node {
    8    int c, x, y;
    9    node(int c, int x, int y) : c(c), x(x), y(y){}
    10};
    11struct edge {
    12    int u, v; double d;
    13    edge(int u, int v, double d) : u(u), v(v), d(d){}
    14    bool operator<(const edge& other) const {
    15        return d < other.d;
    16    }
    17};
    18int find(int x) {
    19    if(parent[x] == x) return x;
    20    return parent[x] = find(parent[x]);
    21}
    22void unite(int x, int y) {
    23    x = find(x), y = find(y);
    24    parent[x] = y;
    25}
    26signed main() {
    27    ios::sync_with_stdio(0); cin.tie(0); 
    28    int n, m; cin >> n >> m;
    29    parent.resize(n + 1);
    30    for (int i = 0; i <= n; i++) parent[i] = i;
    31    vector<node> vv;
    32    vector<edge> e;
    33    for (int i = 0; i < n; i++) {
    34        int c = i + 1, x, y; cin >> x >> y;
    35        vv.emplace_back(c, x, y);
    36    }
    37    for (int i = 0; i < m; i++) {
    38        int x, y; cin >> x >> y;
    39        e.emplace_back(x, y, 0);
    40    }
    41    for (int i = 0; i < vv.size(); i++) {
    42        auto [c, x, y] = vv[i];
    43        for (int j = i + 1; j < vv.size(); j++) {
    44            auto[cc, xx, yy] = vv[j];
    45            double dist = sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
    46            e.emplace_back(c, cc, dist);
    47        }
    48    }
    49    sort(e.begin(), e.end());
    50    int cnt = 0;
    51    double ans = 0;
    52    for (int i = 0; i < e.size(); i++) {
    53        auto[u, v, d] = e[i];
    54        if(find(u) != find(v)){
    55            unite(u, v);
    56            cnt++;
    57            ans += d;
    58        }
    59        if (cnt == n - 1) break;
    60    }
    61    cout << fixed << setprecision(2) << ans << '\n';
    62    return 0;
    63}