Codeforces Round #597 DIV2 D問題 (1750pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, X[2000], Y[2000], C[2000], K[2000];
int vis[2000], bk[2000]; ll mn[2000];
ll res;
int ps, p[2000], ms, ma[2000], mb[2000];
{
int i, j, k;
ll cost;
rd(N, (X,Y)(N), C(N), K(N));
rep(i,N) mn[i] = C[i], bk[i] = N;
for(;;){
i = argmin(mn(N));
if(vis[i]++) break;
res += mn[i];
mn[i] = ll_inf;
if(bk[i]==N) p[ps++] = i;
else arrInsert(ms,ms,ma,i,mb,bk[i]);
rep(k,N) if(vis[k]==0){
cost = (ll) (K[i] + K[k]) * (abs(X[i]-X[k]) + abs(Y[i]-Y[k]));
if(mn[k] > cost) mn[k] = cost, bk[k] = i;
}
}
wt(res);
wt(ps);
wt(p(ps)+1);
wt(ms);
rep(i,ms) wt(ma[i]+1, mb[i]+1);
}
Current time: 2024年04月24日06時47分00秒
Last modified: 2019年11月02日02時57分06秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF597 CF_Div2_D
トップページに戻る
Logged in as: unknown user (not login)