結果
| 問題 | No.867 避難経路 |
| ユーザー |
 noshi91
|
| 提出日時 | 2019-08-16 23:30:47 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,798 bytes |
| コンパイル時間 | 791 ms |
| コンパイル使用メモリ | 80,876 KB |
| 最終ジャッジ日時 | 2024-11-14 21:34:19 |
| 合計ジャッジ時間 | 6,337 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'void n91::main_()':
main.cpp:120:32: error: 'numeric_limits' is not a member of 'std'
120 | auto d = md_vec(h, w, std::numeric_limits<u64>::max());
| ^~~~~~~~~~~~~~
main.cpp:120:50: error: expected primary-expression before '>' token
120 | auto d = md_vec(h, w, std::numeric_limits<u64>::max());
| ^
main.cpp:120:53: error: '::max' has not been declared; did you mean 'std::max'?
120 | auto d = md_vec(h, w, std::numeric_limits<u64>::max());
| ^~~
| std::max
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/algorithm:61,
from main.cpp:77:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algo.h:5756:5: note: 'std::max' declared here
5756 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
main.cpp:133:44: error: 'numeric_limits' is not a member of 'std'
133 | std::fill(v.begin(), v.end(), std::numeric_limits<u64>::max());
| ^~~~~~~~~~~~~~
main.cpp:133:62: error: expected primary-expression before '>' token
133 | std::fill(v.begin(), v.end(), std::numeric_limits<u64>::max());
| ^
main.cpp:133:65: error: '::max' has not been declared; did you mean 'std::max'?
133 | std::fill(v.begin(), v.end(), std::numeric_limits<u64>::max());
| ^~~
| std::max
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algo.h:5756:5: note: 'std::max' declared here
5756 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
main.cpp:169:16: erro
ソースコード
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <vector>
namespace n91 {
using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
constexpr usize operator"" _z(unsigned long long x) noexcept {
return static_cast<usize>(x);
}
class rep {
const usize f, l;
public:
class itr {
friend rep;
usize i;
constexpr itr(const usize x) noexcept : i(x) {}
public:
void operator++() noexcept { ++i; }
constexpr usize operator*() const noexcept { return i; }
constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
};
constexpr rep(const usize first, const usize last) noexcept
: f(first), l(last) {}
constexpr itr begin() const noexcept { return itr(f); }
constexpr itr end() const noexcept { return itr(l); }
};
class revrep {
const usize f, l;
public:
class itr {
friend revrep;
usize i;
constexpr itr(usize x) noexcept : i(x) {}
public:
void operator++() noexcept { --i; }
constexpr usize operator*() const noexcept { return i; }
constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
};
constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
constexpr itr begin() const noexcept { return itr(l); }
constexpr itr end() const noexcept { return itr(f); }
};
template <class T> using vec_alias = std::vector<T>;
template <class T> auto md_vec(const usize n, const T &value) {
return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) {
return a < b ? b - a : a - b;
}
template <class T> T scan() {
T ret;
std::cin >> ret;
return ret;
}
} // namespace n91
#include <algorithm>
#include <array>
#include <iostream>
#include <queue>
#include <utility>
namespace n91 {
void main_() {
static constexpr u64 MaxK = static_cast<u64>(300);
const auto h = scan<usize>();
const auto w = scan<usize>();
const usize gx = scan<usize>() - 1_z;
const usize gy = scan<usize>() - 1_z;
auto a = md_vec(h, w, static_cast<u64>(0));
for (auto &v : a) {
for (auto &e : v) {
e = scan<u64>();
}
}
const usize q = scan<usize>();
struct query_type {
usize x, y;
u64 k;
u64 ans;
};
std::vector<query_type> query(q);
for (auto &e : query) {
e.x = scan<usize>() - 1_z;
e.y = scan<usize>() - 1_z;
e.k = scan<u64>();
}
std::array<std::vector<usize>, static_cast<usize>(MaxK)> small;
for (const auto i : rep(0_z, q)) {
if (query[i].k < MaxK) {
small[query[i].k].push_back(i);
}
}
{
auto d = md_vec(h, w, std::numeric_limits<u64>::max());
struct node_type {
usize x, y;
u64 c;
constexpr node_type(const usize x, const usize y, const u64 c)
: x(x), y(y), c(c) {}
constexpr bool operator<(const node_type &rhs) const noexcept {
return rhs.c < c;
}
};
std::priority_queue<node_type> que;
for (const auto k : rep(1_z, static_cast<usize>(MaxK))) {
for (auto &v : d) {
std::fill(v.begin(), v.end(), std::numeric_limits<u64>::max());
}
const u64 kk = static_cast<u64>(k * k);
std::array<usize, 4_z> dx{-1_z, 0_z, 0_z, 1_z}, dy{0_z, -1_z, 1_z, 0_z};
que.emplace(gx, gy, static_cast<u64>(0));
d[gx][gy] = static_cast<u64>(0);
while (!que.empty()) {
const usize x = que.top().x;
const usize y = que.top().y;
const u64 c = que.top().c;
que.pop();
if (d[x][y] < c) {
continue;
}
const u64 nc = c + a[x][y] + kk;
for (const auto i : rep(0_z, 4_z)) {
const usize nx = x + dx[i];
const usize ny = y + dy[i];
if (nx < h && ny < w && d[nx][ny] > nc) {
d[nx][ny] = nc;
que.emplace(nx, ny, nc);
}
}
}
for (const auto i : small[k]) {
auto &e = query[i];
e.ans = d[e.x][e.y] + a[e.x][e.y] + kk;
}
}
}
{
using p = std::pair<usize, u64>;
auto d = md_vec(
h, w,
p(std::numeric_limits<usize>::max(), std::numeric_limits<u64>::max()));
std::array<usize, 4_z> dx{-1_z, 0_z, 0_z, 1_z}, dy{0_z, -1_z, 1_z, 0_z};
struct node_type {
usize x, y;
p c;
constexpr node_type(const usize x, const usize y, const p c)
: x(x), y(y), c(c) {}
constexpr bool operator<(const node_type &rhs) const noexcept {
return rhs.c < c;
}
};
std::priority_queue<node_type> que;
que.emplace(gx, gy, p(0_z, static_cast<u64>(0)));
d[gx][gy] = {0_z, static_cast<u64>(0)};
while (!que.empty()) {
const usize x = que.top().x;
const usize y = que.top().y;
const p c = que.top().c;
que.pop();
if (d[x][y] < c) {
continue;
}
const p nc = p(c.first + 1_z, c.second + a[x][y]);
for (const auto i : rep(0_z, 4_z)) {
const usize nx = x + dx[i];
const usize ny = y + dy[i];
if (nx < h && ny < w && d[nx][ny] > nc) {
d[nx][ny] = nc;
que.emplace(nx, ny, nc);
}
}
}
for (auto &e : query) {
if (e.k >= MaxK) {
const usize len = d[e.x][e.y].first + 1_z;
const u64 dist = d[e.x][e.y].second + a[e.x][e.y];
e.ans = dist + e.k * e.k * len;
}
}
}
for (const auto &e : query) {
std::cout << e.ans << std::endl;
}
}
} // namespace n91
int main() {
n91::main_();
return 0;
}