SRM409 Div2 Hard

1000

やるだけ

const int N = 50 + 1;
vector<int> g[N];

bool T[N];

int f(int node)
{
  int cost[node];
  fill(cost, cost + node, 1 << 29);
  cost[0] = 0;

  queue<int> q;

  for (int i = 1; i < (int)node; ++i) {
    if (T[i]) {
      q.push(i);
      cost[i] = 0;
    }
  }

  for (q.push(0); q.size(); q.pop()) {
    int n = q.front();
    each (i, g[n]) {
      if (cost[*i] > cost[n] + 1) {
        cost[*i] = cost[n] + 1;
        q.push(*i);
      }
    }
  }

  return *max_element(cost, cost + node);
}

int rec(int i, int tc, int node)
{
  if (tc == 0) return f(node);
  int mn = 1 << 28;
  for (; i < node; ++i) {
    T[i] = true;
    mn = min(mn, rec(i + 1, tc - 1, node));
    T[i] = false;
  }
  return mn;
}

class TeleportsNetwork {
public:
  int distribute(int tc, vector <int> X, vector <int> Y)
  {
    fill(T, T + N, false);
    fill(g, g + N, vector<int>());

    const int node = X.size();

    double d[node][node];

    for (int i = 0; i < (int)node; ++i) {
      for (int j = 0; j < (int)node; ++j) {
        double x = X[i] - X[j];
        double y = Y[i] - Y[j];
        d[i][j] = sqrt(x * x + y * y);
      }
    }

    for (int i = 1; i < (int)node; ++i) {
      double dist = 1e126;
      int idx;
      for (int j = 0; j < (int)node; ++j) {
        if (d[0][i] < d[0][j]) continue;
        if (i == j) continue;
        if (d[i][j] < dist) {
          dist = d[i][j];
          idx = j;
        }
        if (dist == d[i][j]) {
          if (X[j] < X[idx]) idx = j;
          if (X[j] == X[idx] && Y[j] < Y[idx]) idx = j;
        }
      }
      g[i].push_back(idx);
      g[idx].push_back(i);
    }

    return rec(1, tc, node);
  }
};