結果
問題 | No.867 避難経路 |
ユーザー |
![]() |
提出日時 | 2019-08-16 22:22:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,527 ms / 6,000 ms |
コード長 | 2,063 bytes |
コンパイル時間 | 1,982 ms |
コンパイル使用メモリ | 186,836 KB |
実行使用メモリ | 178,176 KB |
最終ジャッジ日時 | 2024-09-22 18:21:03 |
合計ジャッジ時間 | 93,573 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}std::pair<int, int> dirs[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};int main() {int h = ri(), w = ri();int gx = ri() - 1, gy = ri() - 1;int a[h][w];for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) a[i][j] = ri();using T = std::pair<int64_t, std::pair<int, int> >;std::vector<std::vector<int64_t> > dist[350];for (int i = 1; i < 350; i++) {int64_t cost_base = i * i;dist[i].resize(h, std::vector<int64_t>(w, 1000000000000000000));std::priority_queue<T, std::vector<T>, std::greater<T> > que;que.push({a[gx][gy] + cost_base, {gx, gy}});dist[i][gx][gy] = a[gx][gy] + cost_base;while (que.size()) {auto cur = que.top();que.pop();for (auto d : dirs) {int x = cur.second.first + d.first;int y = cur.second.second + d.second;if (x < 0 || x >= h || y < 0 || y >= w) continue;int64_t new_cost = cur.first + cost_base + a[x][y];if (dist[i][x][y] > new_cost) {dist[i][x][y] = new_cost;que.push({new_cost, {x, y}});}}}}std::vector<std::vector<int64_t> > normal_dist(h, std::vector<int64_t>(w, 1000000000000000000));normal_dist[gx][gy] = a[gx][gy];std::queue<std::pair<int, int> > que;que.push({gx, gy});while (que.size()) {auto cur = que.front();que.pop();for (auto d : dirs) {int x = cur.first + d.first;int y = cur.second + d.second;if (x < 0 || x >= h || y < 0 || y >= w) continue;if (std::abs(cur.first - gx) + std::abs(cur.second - gy) >= std::abs(x - gx) + std::abs(y - gy)) continue;int64_t new_cost = normal_dist[cur.first][cur.second] + a[x][y];if (normal_dist[x][y] > new_cost) {normal_dist[x][y] = new_cost;que.push({x, y});}}}int q = ri();for (int i = 0; i < q; i++) {int x = ri() - 1;int y = ri() - 1;int k = ri();if (k < 350) {std::cout << dist[k][x][y] << std::endl;} else std::cout << normal_dist[x][y] + (int64_t) k * k * (std::abs(x - gx) + std::abs(y - gy) + 1) << std::endl;}return 0;}