結果
問題 | No.867 避難経路 |
ユーザー | lumc_ |
提出日時 | 2019-08-17 06:23:09 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,120 ms / 6,000 ms |
コード長 | 2,053 bytes |
コンパイル時間 | 2,743 ms |
コンパイル使用メモリ | 113,784 KB |
実行使用メモリ | 113,048 KB |
最終ジャッジ日時 | 2023-10-24 23:41:28 |
合計ジャッジ時間 | 40,457 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
8,456 KB |
testcase_01 | AC | 5 ms
8,456 KB |
testcase_02 | AC | 6 ms
8,456 KB |
testcase_03 | AC | 5 ms
8,456 KB |
testcase_04 | AC | 6 ms
8,456 KB |
testcase_05 | AC | 5 ms
8,456 KB |
testcase_06 | AC | 6 ms
8,456 KB |
testcase_07 | AC | 6 ms
8,456 KB |
testcase_08 | AC | 6 ms
8,456 KB |
testcase_09 | AC | 6 ms
8,456 KB |
testcase_10 | AC | 6 ms
8,456 KB |
testcase_11 | AC | 6 ms
8,456 KB |
testcase_12 | AC | 5 ms
8,456 KB |
testcase_13 | AC | 6 ms
8,456 KB |
testcase_14 | AC | 5 ms
8,456 KB |
testcase_15 | AC | 1,112 ms
112,556 KB |
testcase_16 | AC | 1,045 ms
113,044 KB |
testcase_17 | AC | 1,108 ms
113,048 KB |
testcase_18 | AC | 1,039 ms
113,044 KB |
testcase_19 | AC | 1,036 ms
113,044 KB |
testcase_20 | AC | 1,017 ms
113,044 KB |
testcase_21 | AC | 1,014 ms
113,044 KB |
testcase_22 | AC | 1,042 ms
113,044 KB |
testcase_23 | AC | 1,090 ms
113,048 KB |
testcase_24 | AC | 1,011 ms
113,044 KB |
testcase_25 | AC | 1,010 ms
113,044 KB |
testcase_26 | AC | 1,044 ms
113,008 KB |
testcase_27 | AC | 1,036 ms
113,048 KB |
testcase_28 | AC | 1,072 ms
113,024 KB |
testcase_29 | AC | 1,120 ms
113,024 KB |
testcase_30 | AC | 849 ms
113,020 KB |
testcase_31 | AC | 868 ms
113,044 KB |
testcase_32 | AC | 871 ms
113,044 KB |
testcase_33 | AC | 845 ms
113,044 KB |
testcase_34 | AC | 867 ms
113,040 KB |
testcase_35 | AC | 917 ms
113,040 KB |
testcase_36 | AC | 915 ms
112,924 KB |
testcase_37 | AC | 867 ms
112,116 KB |
testcase_38 | AC | 859 ms
112,224 KB |
testcase_39 | AC | 895 ms
112,092 KB |
testcase_40 | AC | 851 ms
112,208 KB |
testcase_41 | AC | 17 ms
80,084 KB |
testcase_42 | AC | 18 ms
80,472 KB |
testcase_43 | AC | 18 ms
80,472 KB |
ソースコード
// includes {{{ #include<iostream> #include<iomanip> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<tuple> #include<cmath> #include<random> #include<cassert> #include<bitset> #include<cstdlib> // #include<deque> // #include<multiset> // #include<cstring> // #include<bits/stdc++.h> // }}} using namespace std; using ll = long long; // 右下にゴールがあるとする // 右下に向かわなかった場合,2 * k^2 の損をする // 得の最大値は 98 * 248 = 24304 = M // M < 2 * k^2 <=> k >= 111 = K // 最短路 // N^2 * log(N^2) * K int h, w; int gx, gy; ll A[250][250]; int q; constexpr int K = 111; constexpr ll inf = 1e18; ll dist[K+1][250][250]; ll steps[K+1][250][250]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> h >> w; cin >> gx >> gy; gx--, gy--; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) cin >> A[i][j]; for(int k = 1; k <= K; k++) { for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) dist[k][i][j] = inf; using P = tuple<ll, int, int, int>; priority_queue<P, vector<P>, greater<P>> pq; dist[k][gx][gy] = k * k + A[gx][gy]; steps[k][gx][gy] = 1; pq.emplace(dist[k][gx][gy], gx, gy, 1); while(pq.size()) { ll d; int x, y, s; tie(d, x, y, s) = pq.top(); pq.pop(); if(dist[k][x][y] < d) continue; for(int dir = 0; dir < 4; dir++) { int nx = x + dx[dir]; int ny = y + dy[dir]; if(0 <= nx and nx < h and 0 <= ny and ny < w); else continue; ll nd = d + k * k + A[nx][ny]; if(nd < dist[k][nx][ny]) { dist[k][nx][ny] = nd; steps[k][nx][ny] = s + 1; pq.emplace(nd, nx, ny, s + 1); } } } } cin >> q; for(int i = 0; i < q; i++) { ll x, y, k; cin >> x >> y >> k; x--, y--; ll r = min<ll>(K, k); ll ans = dist[r][x][y] + (k * k - r * r) * steps[r][x][y]; cout << ans << "\n"; } return 0; }