結果
問題 | 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; }