yukicoder No.867 - 避難経路

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLayversion 20190820-1)のコード

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)

ログイン: