AOJ 1127 Building a Space Station
問題
たくさんのなんかコロニーみたいなのがあって、全部のコロニーに行ったり来たりできるようにしたい。
各コロニーの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; }
英語できないと競プロが捗らないですね