結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-08-06 21:44:45 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,601 bytes |
コンパイル時間 | 3,612 ms |
コンパイル使用メモリ | 263,688 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-17 01:37:16 |
合計ジャッジ時間 | 4,679 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <bits/stdc++.h> using namespace std; using vertex = tuple<int64_t, int, int>; constexpr int64_t inf = 1e18; vector<int> dx{-1, 1, 0, 0}, dy{0, 0, 1, -1}, cost(4); int main() { int h, w; cin >> h >> w; for (int i = 0; i < 4; i++) { cin >> cost.at(i); } int64_t k, p; cin >> k >> p; int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty; sx--; sy--; tx--; ty--; vector<string> c(h); for (auto &&s : c) { cin >> s; } vector total(h, vector<int64_t>(w, inf)); priority_queue<vertex, vector<vertex>, greater<vertex>> q; q.emplace(0, sx, sy); while (not q.empty()) { auto [d0, x, y] = q.top(); q.pop(); if (d0 >= total.at(x).at(y)) { continue; } total.at(x).at(y) = d0; for (int i = 0; i < 4; i++) { int64_t x_next = x + dx.at(i), y_next = y + dy.at(i), d_next = d0 + cost.at(i); if (x_next < 0 or h <= x_next or y_next < 0 or w <= y_next) { continue; } if (c.at(x_next).at(y_next) == '#') { continue; } if (c.at(x_next).at(y_next) == '@') { d_next += p; } if (d_next >= total.at(x_next).at(y_next)) { continue; } q.emplace(d_next, x_next, y_next); } } if (total.at(tx).at(ty) <= k) { puts("Yes"); } else { puts("No"); } return 0; }