読者です 読者をやめる 読者になる 読者になる

AOJ 1127 Building a Space Station

C/C++ Algorithms AOJ Graph

問題

たくさんのなんかコロニーみたいなのがあって、全部のコロニーに行ったり来たりできるようにしたい。

各コロニーのx,y,z座標と半径rが与えられるのでコロニー間に設置する道の最短総距離を求める。

解法

似たような座標から距離求めて最短経路を求める問題を前にやった。

今回は最小全域木を求める。プリム法でやった。

コード

int n;
double cost[128][128];
double mincost[128];
bool used[128];

double prim(){
  rep(i, n){
    mincost[i] = INF;
    used[i] = false;
  }

  mincost[0] = 0;
  double res = 0;

  while(true){
    int v = -1;
    rep(u, n){
      if(!used[u] && (v == -1 || mincost[u] < mincost[v]))  v = u;
    }

    if(v == -1) break;
    used[v] = true;
    res += mincost[v];


    rep(u, n)
      mincost[u] = min(mincost[u], cost[v][u]);
  }
  return res;
}

int main(){
  while(scanf("%d", &n) && n){
    double x[128], y[128], z[128], r[128];
    rep(i, n){
      scanf("%lf%lf%lf%lf", x+i, y+i, z+i, r+i);
    }
    rep(i, n) rep(j, n) cost[i][j] = INF;

    rep(i, n) REP(j, i+1, n){
      double dis = sqrt(SQ(x[i]-x[j])+SQ(y[i]-y[j])+SQ(z[i]-z[j]));
      dis -= r[i] + r[j];
      dis = max(dis, 0.0);
      cost[i][j] = cost[j][i] = dis;
    }

    printf("%.3lf\n", prim());
  }
  return 0;
}

英語できないと競プロが捗らないですね