結果
問題 | No.867 避難経路 |
ユーザー | 👑 hos.lyric |
提出日時 | 2019-08-16 22:09:48 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,149 ms / 6,000 ms |
コード長 | 3,694 bytes |
コンパイル時間 | 3,605 ms |
コンパイル使用メモリ | 127,576 KB |
実行使用メモリ | 132,192 KB |
最終ジャッジ日時 | 2023-10-24 00:18:23 |
合計ジャッジ時間 | 68,229 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 22 ms
89,552 KB |
testcase_01 | AC | 21 ms
89,552 KB |
testcase_02 | AC | 21 ms
89,552 KB |
testcase_03 | AC | 21 ms
89,552 KB |
testcase_04 | AC | 21 ms
89,552 KB |
testcase_05 | AC | 21 ms
89,552 KB |
testcase_06 | AC | 20 ms
89,552 KB |
testcase_07 | AC | 21 ms
89,552 KB |
testcase_08 | AC | 21 ms
89,552 KB |
testcase_09 | AC | 21 ms
89,552 KB |
testcase_10 | AC | 21 ms
89,552 KB |
testcase_11 | AC | 21 ms
89,552 KB |
testcase_12 | AC | 21 ms
89,552 KB |
testcase_13 | AC | 22 ms
89,552 KB |
testcase_14 | AC | 22 ms
89,552 KB |
testcase_15 | AC | 2,149 ms
130,464 KB |
testcase_16 | AC | 2,041 ms
132,144 KB |
testcase_17 | AC | 2,131 ms
132,148 KB |
testcase_18 | AC | 2,123 ms
131,408 KB |
testcase_19 | AC | 2,042 ms
132,148 KB |
testcase_20 | AC | 2,011 ms
131,104 KB |
testcase_21 | AC | 1,969 ms
131,216 KB |
testcase_22 | AC | 2,011 ms
131,216 KB |
testcase_23 | AC | 2,087 ms
131,216 KB |
testcase_24 | AC | 1,978 ms
131,216 KB |
testcase_25 | AC | 1,990 ms
131,216 KB |
testcase_26 | AC | 2,012 ms
131,216 KB |
testcase_27 | AC | 2,018 ms
131,216 KB |
testcase_28 | AC | 1,943 ms
131,200 KB |
testcase_29 | AC | 2,042 ms
131,264 KB |
testcase_30 | AC | 1,597 ms
131,200 KB |
testcase_31 | AC | 1,658 ms
131,216 KB |
testcase_32 | AC | 1,633 ms
131,216 KB |
testcase_33 | AC | 1,636 ms
131,216 KB |
testcase_34 | AC | 1,683 ms
131,196 KB |
testcase_35 | AC | 1,831 ms
131,468 KB |
testcase_36 | AC | 1,765 ms
131,504 KB |
testcase_37 | AC | 1,655 ms
132,136 KB |
testcase_38 | AC | 1,638 ms
132,140 KB |
testcase_39 | AC | 1,622 ms
132,144 KB |
testcase_40 | AC | 1,621 ms
132,192 KB |
testcase_41 | AC | 27 ms
128,760 KB |
testcase_42 | AC | 27 ms
128,784 KB |
testcase_43 | AC | 30 ms
128,784 KB |
ソースコード
#pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx") #include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> void chmin(T &t, const T &f) { if (t > f) t = f; } template <class T> void chmax(T &t, const T &f) { if (t < f) t = f; } constexpr Int INF = 1001001001001001001LL; constexpr int MAX = 260; constexpr int L = 224; int H, W; int GX, GY; Int A[MAX][MAX]; int Q; int X[500010], Y[500010]; Int K[500010]; Int dist[L + 10][MAX][MAX]; Int dp[MAX][MAX]; int main() { for (; ~scanf("%d%d", &H, &W); ) { scanf("%d%d", &GX, &GY); --GX; --GY; for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) { scanf("%lld", &A[x][y]); } scanf("%d", &Q); for (int q = 0; q < Q; ++q) { scanf("%d%d%lld", &X[q], &Y[q], &K[q]); --X[q]; --Y[q]; } // small for (int k = 0; k < L; ++k) { const Int k2 = 1LL * k * k; using Node = pair<Int, pair<int, int>>; priority_queue<Node, vector<Node>, greater<Node>> q; for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) { dist[k][x][y] = INF; } dist[k][GX][GY] = k2 + A[GX][GY]; q.emplace(dist[k][GX][GY], make_pair(GX, GY)); for (; !q.empty(); ) { const Int c = q.top().first; const int x = q.top().second.first; const int y = q.top().second.second; q.pop(); if (dist[k][x][y] == c) { auto update = [&](int xx, int yy) { const Int cc = c + k2 + A[xx][yy]; if (dist[k][xx][yy] > cc) { dist[k][xx][yy] = cc; q.emplace(cc, make_pair(xx, yy)); } }; if (x + 1 < H) update(x + 1, y); if (y + 1 < W) update(x, y + 1); if (x - 1 >= 0) update(x - 1, y); if (y - 1 >= 0) update(x, y - 1); } } } // large for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) { dp[x][y] = INF; } dp[GX][GY] = A[GX][GY]; for (int x = GX; x < H; ++x) for (int y = GY; y < W; ++y) { if (x > GX) chmin(dp[x][y], dp[x - 1][y] + A[x][y]); if (y > GY) chmin(dp[x][y], dp[x][y - 1] + A[x][y]); } for (int x = GX; x < H; ++x) for (int y = GY; y >= 0; --y) { if (x > GX) chmin(dp[x][y], dp[x - 1][y] + A[x][y]); if (y < GY) chmin(dp[x][y], dp[x][y + 1] + A[x][y]); } for (int x = GX; x >= 0; --x) for (int y = GY; y < W; ++y) { if (x < GX) chmin(dp[x][y], dp[x + 1][y] + A[x][y]); if (y > GY) chmin(dp[x][y], dp[x][y - 1] + A[x][y]); } for (int x = GX; x >= 0; --x) for (int y = GY; y >= 0; --y) { if (x < GX) chmin(dp[x][y], dp[x + 1][y] + A[x][y]); if (y < GY) chmin(dp[x][y], dp[x][y + 1] + A[x][y]); } for (int q = 0; q < Q; ++q) { Int ans; if (K[q] < L) { ans = dist[K[q]][X[q]][Y[q]]; } else { ans = 1LL * K[q] * K[q] * (1 + abs(X[q] - GX) + abs(Y[q] - GY)) + dp[X[q]][Y[q]]; } printf("%lld\n", ans); } } return 0; }