結果

問題 No.867 避難経路
コンテスト
ユーザー ngtkana
提出日時 2019-08-16 23:46:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,035 bytes
コンパイル時間 3,196 ms
コンパイル使用メモリ 216,252 KB
最終ジャッジ日時 2025-01-07 13:06:39
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 15 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

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;
  int max = h * w;
  auto dp = make_higher_vector<2, std::vector<std::pair<int, int>>>(h, w);
  int di[4] = {-1, +1, 0, 0};
  int dj[4] = {0, 0, -1, +1};
  std::queue<std::tuple<int, int, int, int>> que;
  que.emplace(gx, gy, 1, at(a, gx, gy));
  while (!que.empty())
  {
    int i, j, k, val; std::tie(i, j, k, val) = que.front(); que.pop();
    if (k > max) break;
    auto& crr = at(dp, i, j);
    if (!crr.empty() && (crr.back().second <= val)) continue;
    if (!crr.empty() && crr.back().first == k) crr.pop_back();
    crr.emplace_back(k, val);
    for (int l = 0; l < 4; l++)
    {
      int nxi = i + di[l];
      int nxj = j + dj[l];
      if (nxi < 0 || h <= nxi || nxj < 0 || w <= nxj) continue;
      auto nxt_val = val + at(a, nxi, nxj);
      auto& nxt = at(dp, nxi, nxj);
      if (!nxt.empty() && (nxt.back().second <= nxt_val)) continue;
      que.emplace(nxi, nxj, k + 1, nxt_val);
    }
  }
  constexpr int inf = 1 << 30;
  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 (auto pair : at(dp, x, y))
    {
      long long k, val; std::tie(k, val) = pair;
      cmn(ret, k * level * level + val);
    }
    std::cout << ret << std::endl;
  }
  return 0;
}
0