結果
問題 | No.867 避難経路 |
ユーザー | paruki |
提出日時 | 2019-08-17 17:58:10 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 4,575 ms / 6,000 ms |
コード長 | 2,561 bytes |
コンパイル時間 | 1,920 ms |
コンパイル使用メモリ | 188,496 KB |
実行使用メモリ | 20,068 KB |
最終ジャッジ日時 | 2023-10-25 00:10:09 |
合計ジャッジ時間 | 77,641 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 2 ms
4,348 KB |
testcase_12 | AC | 2 ms
4,348 KB |
testcase_13 | AC | 2 ms
4,348 KB |
testcase_14 | AC | 3 ms
4,348 KB |
testcase_15 | AC | 2,362 ms
19,920 KB |
testcase_16 | AC | 2,279 ms
19,948 KB |
testcase_17 | AC | 2,416 ms
20,020 KB |
testcase_18 | AC | 2,342 ms
20,068 KB |
testcase_19 | AC | 2,255 ms
20,052 KB |
testcase_20 | AC | 939 ms
17,616 KB |
testcase_21 | AC | 929 ms
17,612 KB |
testcase_22 | AC | 931 ms
18,000 KB |
testcase_23 | AC | 947 ms
18,156 KB |
testcase_24 | AC | 930 ms
18,048 KB |
testcase_25 | AC | 1,040 ms
17,684 KB |
testcase_26 | AC | 1,037 ms
17,688 KB |
testcase_27 | AC | 1,040 ms
17,684 KB |
testcase_28 | AC | 1,031 ms
17,684 KB |
testcase_29 | AC | 1,050 ms
17,680 KB |
testcase_30 | AC | 3,921 ms
17,468 KB |
testcase_31 | AC | 4,575 ms
18,764 KB |
testcase_32 | AC | 4,355 ms
18,740 KB |
testcase_33 | AC | 4,251 ms
18,748 KB |
testcase_34 | AC | 4,117 ms
17,464 KB |
testcase_35 | AC | 4,396 ms
17,464 KB |
testcase_36 | AC | 4,411 ms
17,588 KB |
testcase_37 | AC | 4,094 ms
17,300 KB |
testcase_38 | AC | 4,103 ms
17,300 KB |
testcase_39 | AC | 4,069 ms
17,300 KB |
testcase_40 | AC | 4,008 ms
17,300 KB |
testcase_41 | AC | 3 ms
4,376 KB |
testcase_42 | AC | 3 ms
4,376 KB |
testcase_43 | AC | 2 ms
4,376 KB |
ソースコード
#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 return using 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; }