結果
問題 | No.867 避難経路 |
ユーザー |
|
提出日時 | 2019-08-17 17:58:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,562 ms / 6,000 ms |
コード長 | 2,561 bytes |
コンパイル時間 | 2,167 ms |
コンパイル使用メモリ | 188,344 KB |
実行使用メモリ | 19,996 KB |
最終ジャッジ日時 | 2024-09-24 19:12:06 |
合計ジャッジ時間 | 77,547 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#define _USE_MATH_DEFINES#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define MT make_tuple#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()#define RT returnusing ll = long long;using pii = pair<int, int>;using vi = vector<int>;using vll = vector<ll>;template<class Val>vector<vector<Val> > dijkstraGrid(vector<vector<Val>> grid, int sy, int sx) {const int h = (int)grid.size();const int w = (int)grid[0].size();static const int DIR[] = { 0,-1,0,1,0 };vector<vector<Val> > res(h, vector<Val>(w, -1));priority_queue<tuple<Val, int, int> > Q;Q.push({ -grid[sy][sx], sy, sx });while (!Q.empty()) {Val negaDis;int y, x;tie(negaDis, y, x) = Q.top();Q.pop();if (res[y][x] >= 0)continue;res[y][x] = -negaDis;rep(i, 4) {int ny = y + DIR[i];int nx = x + DIR[i + 1];if (ny >= 0 && ny < h && nx >= 0 && nx < w && res[ny][nx] < 0) {Q.push({ negaDis - grid[ny][nx],ny,nx });}}}return res;}struct Query {int id, k, y, x;};void solve() {int H, W;cin >> H >> W;int gy, gx;cin >> gy >> gx;--gy;--gx;vector<vll> A(H, vll(W));rep(y, H) {rep(x, W)cin >> A[y][x];}const int LIM = 250;int Q;cin >> Q;vector<Query> qs[LIM];rep(i, Q) {int y, x, k;cin >> y >> x >> k;qs[k < LIM ? k : 0].push_back(Query{ i,k,--y,--x });}const int MOD = LIM * LIM;vll ans(Q);vector<vll> B = A;rep(y, H)rep(x, W)B[y][x] += MOD;auto dis = dijkstraGrid(B, gy, gx);each(q, qs[0]) {ll z = dis[q.y][q.x];ll kCnt = z / MOD;ll aSum = z % MOD;ans[q.id] = kCnt * q.k * q.k + aSum;}FOR(i, 1, LIM) {if (qs[i].empty())continue;rep(y, H)rep(x, W) {B[y][x] = i * i + A[y][x];}dis = dijkstraGrid(B, gy, gx);each(q, qs[i]) {ans[q.id] = dis[q.y][q.x];}}each(a, ans) {cout << a << endl;}}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);solve();return 0;}