結果

問題 No.867 避難経路
ユーザー ngtkana
提出日時 2019-08-16 23:02:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 3,698 bytes
コンパイル時間 2,743 ms
コンパイル使用メモリ 205,300 KB
最終ジャッジ日時 2025-01-07 12:44:29
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 MLE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_geneous = 0; ngtkana_is_geneous < n; ngtkana_is_geneous++)
#define rep(i, begin, end) for(int i = begin; i < end; i++)

#define LOCAL
using std::to_string;
auto to_string(std::string s) -> std::string {
  return '"' + s + '"';
}
auto to_string(char c) -> std::string {
  return "'" + std::string{c} + "'";
}
auto to_string(const char* s) -> std::string {
  return to_string((std::string) s);
}
auto to_string(bool b) -> std::string {
  return (b ? "true" : "false");
}
template <typename T, typename U>
auto to_string(std::pair<T, U> p) -> std::string {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <size_t N>
auto to_string(std::bitset<N> bs) -> std::string {
  std::string res{};
  for (size_t i = 0; i < N; i++)
    res.insert(res.begin(), bs.test(i) ? '1' : '0');
  return res;
}
template <typename T>
auto to_string(T v) -> std::string {
  bool flg = false;
  std::string res = "{";
  for (auto const&x : v) {
    if (flg) res += ", ";
    else flg = true;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  std::cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template <typename T>
auto make_vector(size_t sz, T t) {
  return std::vector<T>(sz, t);
}
template <size_t N, typename T, typename U, std::enable_if_t<
  N == 1, std::nullptr_t> = nullptr>
auto make_higher_vector(size_t sz, U u) {
  return make_vector(sz, T(u));
}
template <size_t N, typename T, std::enable_if_t<
  N == 1, std::nullptr_t> = nullptr>
auto make_higher_vector(size_t sz) {
  return std::vector<T>(sz);
}
template <size_t N, typename T, typename... Args, std::enable_if_t<
  N != 1, std::nullptr_t> = nullptr>
auto make_higher_vector(size_t a, Args... args) {
  return make_vector(a, make_higher_vector<N - 1, T>(args...));
}
template <typename T, typename Size_t>
auto& at(T& t, Size_t i) {
  return t.at(i);
}
template <typename T, typename Size_t, typename... Args>
auto& at(T& t, Size_t i, Args... args) {
  return at(t.at(i), args...);
}
template<typename T, typename U>
inline auto cmn (T& a, U b) {if (a > b) {a = b; return true;} return false;}
template<typename T, typename U>
inline auto cmx (T& a, U b) {if (a < b) {a = b; return true;} return false;}

int main()
{
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int h, w; std::cin >> h >> w;
  int gx, gy; std::cin >> gx >> gy;
  gx--, gy--;
  auto a = make_higher_vector<2, int>(h, w);
  for (auto & b : a) for (auto & c : b) std::cin >> c;
  constexpr int inf = 1 << 30;
  int max = h * w / 2;
  auto dp = make_higher_vector<3, int>(h, w, max + 1, inf);
  at(dp, gx, gy, 0) = at(a, gx, gy);
  int di[4] = {-1, +1, 0, 0};
  int dj[4] = {0, 0, -1, +1};
  rep(k, 0, max) rep(i, 0, h) rep(j, 0, w)
  {
    auto crr = at(dp, i, j, k);
    if (crr == inf) continue;
    cmn(at(dp, i, j, k + 1), crr);
    for (int l = 0; l < 4; l++)
    {
      auto nxi = i + di[l];
      auto nxj = j + dj[l];
      if (nxi < 0 || h <= nxi || nxj < 0 || w <= nxj) continue;
      cmn(at(dp, nxi, nxj, k + 1), crr + at(a, nxi, nxj));
    }
  }
  int q; std::cin >> q;
  while (q--)
  {
    int x, y; long long level;
    std::cin >> x >> y >> level;
    x--, y--;
    long long ret = inf;
    for (int k = 0; k <= max; k++)
    {
      auto crr = at(dp, x, y, k);
      if (crr == inf) continue;
      cmn(ret, level * level * (k + 1) + crr);
    }
    std::cout << ret << std::endl;
  }
  return 0;
}
0