Submission #19546475

---

Source Code Expand

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

template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }
template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }

class UnionFind {
private:
  int sz;
  vector<int> par, size_;
public:
  UnionFind() {}
  UnionFind(int n) : sz(n), par(sz), size_(sz, 1) {
    iota(par.begin(), par.end(), 0);
  }
  int root(int x) {
    if (par.at(x) == x) return x;
    else return par.at(x) = root(par.at(x));
  }
  void unit(int x,int y) {
    x = root(x), y = root(y);
    if (x == y) return;
    if (size_.at(x) < size_.at(y)) swap(x, y);
    par.at(y) = x;
    size_.at(x) += size_.at(y);
  }
  int size(int x) {
    x = root(x);
    return size_.at(x);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
};

template<typename T> class Kruskal {
public:
  struct edge {
    int u, v;
    T cost;
    bool operator < (const edge& another) const {
      return cost < another.cost;
    }
  };
  vector<edge> es;
  int V;
  Kruskal(int n) : V(n) {}
  void add(int u, int v, T cost) {
    es.push_back((edge) {u, v, cost});
  }
  T solve() {
    UnionFind UF(V);
    T res = 0;
    int cnt = 0;
    sort(es.begin(),es.end());
    for (edge &e : es) {
      if (!UF.same(e.u, e.v)) {
        UF.unit(e.u, e.v);
        res += e.cost;
        cnt++;
        if (cnt == V - 1) break;
      }
    }
    return res;
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector<tuple<int, int, int>> V(N);
  for (int i = 0; i < N; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    V.at(i) = {a, b, c};
  }
  vector<tuple<int, int, int>> V2(M);
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    V2.at(i) = {a, b, c};
  }
  
  double mi = DBL_MAX;
  for (int bit = 0; bit < 1 << M; bit++) {
    int MX = N + __builtin_popcount(bit);
    auto V3 = V;
    for (int i = 0; i < M; i++) {
      if (bit >> i & 1) V3.push_back(V2.at(i));
    }
    Kruskal<double> K(MX);
    for (int i = 0; i < MX; i++) {
      for (int j = 0; j < i; j++) {
        auto [a, b, c] = V3.at(i);
        auto [d, e, f] = V3.at(j);
        if (c == f) K.add(i, j, hypot(a - d, b - e));
        else K.add(i, j, hypot(a - d, b - e) * 10);
      }
    }
    cmin(mi, K.solve());
  }
  cout << fixed << setprecision(6) << mi << '\n';
}

Submission Info

Judge Result