BOJ 1430 - 공격

BOJ 1430 - 공격

탑과의 거리가 $R$이하인 모든 탑들에서 최단거리를 돌린다.

탑과 거리가 $R$ 초과인 탑들은 이 탑들로 에너지를 전송해야 하고, 각 탑마다 처음에 $R$ 이하의 탑들까지의 최단거리중 최단거리를 기록한다.

그리고 최단거리가 $d$ 라면 각각 $\dfrac{D}{2^{d}}$을 더해주고, 거리가 $R$이하인 탑들은 그냥 $D$를 더해준다.

실수오차가 좀 깨름칙하긴 한데 그냥 통과된다.

void solve() {
   int N, R, D, X, Y;
   cin >> N >> R >> D >> X >> Y;
   vector<pi> pos(N);
   for (auto &[x, y]: pos)cin >> x >> y;

   vvi dist(N, vi(N, inf));
   auto reach = [&](int i, int j) {
      int dx = pos[i].fi - pos[j].fi;
      int dy = pos[i].se - pos[j].se;
      if (dx * dx + dy * dy <= R * R) return 1;
      return 0;
   };
   vi start(N);
   for (int i = 0; i < N; i++) {
      int dx = X - pos[i].fi;
      int dy = Y - pos[i].se;
      if (dx * dx + dy * dy <= R * R) {
         start[i] = 1;
      }
   }
   for (int i = 0; i < N; i++) {
      if (start[i]) {
         queue<int> q;
         q.push(i);
         dist[i][i] = 0;
         while (sz(q)) {
            int cur = q.front();
            q.pop();
            for (int to = 0; to < N; to++) {
               if (reach(cur, to) && dist[i][to] > dist[i][cur] + 1) {
                  dist[i][to] = dist[i][cur] + 1;
                  q.push(to);
               }
            }
         }
      }
   }
   debug(dist[0]);
   double ans = 0;
   vi mn_dist(N, inf);
   for (int i = 0; i < N; i++) {
      if (start[i]) {
         for (int j = 0; j < N; j++) {
            if (!start[j]) {
               mina(mn_dist[j], dist[i][j]);
            }
         }
      }
   }

   for (int i = 0; i < N; i++) {
      if (start[i]) ans += D;
      else if (mn_dist[i] != inf) ans += D / pow(2, mn_dist[i]);
   }
   cout.precision(6);
   cout << fixed << ans;
}