省略
省略
C++に変換後のコードはこちら
#define L 230
int X, Y, GX, GY, A[250][250], Q;
int dist[L][250][250];
{
int i, j, k, d;
int di[4] = {-1,1,0,0}, dj[4] = {0,0,-1,1};
int si, sj, ni, nj;
DijkstraHeap<int> hp;
ll res;
rd(X,Y,GX--,GY--);
rep(i,X) rd(A[i](Y));
hp.malloc(X*Y);
rep(k,L){
hp.init(X*Y);
hp.change(GX*Y+GY, (k+1) * (k+1) + A[GX][GY]);
while(hp.size){
i = hp.pop();
si = i / Y;
sj = i % Y;
rep(d,4){
ni = si + di[d];
nj = sj + dj[d];
if(ni < 0 || nj < 0 || ni >= X || nj >= Y) continue;
hp.change(ni*Y+nj, hp.val[i] + (k+1) * (k+1) + A[ni][nj]);
}
}
rep(i,X) rep(j,Y) dist[k][i][j] = hp.val[i*Y+j];
}
rd(Q);
rep(Q){
rd(i--, j--, k);
if(k <= L){
wt(dist[k-1][i][j]);
} else {
res = dist[L-1][i][j] % (L*L);
res += (ll)(dist[L-1][i][j] / (L*L)) * k * k;
wt(res);
}
}
}
Current time: 2024年03月28日18時50分04秒
Last modified: 2019年08月21日06時07分58秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る
Logged in as: unknown user (not login)