結果
問題 | No.20 砂漠のオアシス |
ユーザー | Hydrogen332 |
提出日時 | 2024-11-01 01:43:18 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 2,216 bytes |
コンパイル時間 | 2,724 ms |
コンパイル使用メモリ | 215,000 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-01 01:43:23 |
合計ジャッジ時間 | 4,332 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, s, e) for (int i = (int)s; i < (int)e; ++i)#define all(a) (a).begin(), (a).end()vector<int> dx = {0, 1, 0, -1};vector<int> dy = {1, 0, -1, 0};template<typename T> bool chmin(T& a, const T& b) {if (a > b) {a = b;return true;}else return false;}int main() {cin.tie(nullptr);int N, V, Ox, Oy;cin >> N >> V >> Ox >> Oy;vector L(N, vector<int>(N));rep(i, 0, N) rep(j, 0, N) cin >> L[i][j];vector d(N, vector<int>(N, 1 << 25));priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> que;d[0][0] = 0;que.push({0, {0, 0}});while (!que.empty()) {int dist;pair<int, int> v;tie(dist, v) = que.top();que.pop();if (dist > d[v.first][v.second]) continue;rep(i, 0, 4) {int x = v.second + dx[i];int y = v.first + dy[i];if (x < 0 || N <= x || y < 0 || N <= y) continue;if (chmin(d[y][x], d[v.first][v.second] + L[y][x])) {que.push({d[y][x], {y, x}});}}}if (V - d[N - 1][N - 1] > 0) {cout << "YES\n";return 0;} else if (Ox == 0 && Oy == 0) {cout << "NO\n";return 0;}V -= d[Oy - 1][Ox - 1];V *= 2;vector d2(N, vector<int>(N, 1 << 25));d2[Oy - 1][Ox - 1] = 0;que.push({0, {Oy - 1, Ox - 1}});while (!que.empty()) {int dist;pair<int, int> v;tie(dist, v) = que.top();que.pop();if (dist > d2[v.first][v.second]) continue;rep(i, 0, 4) {int x = v.second + dx[i];int y = v.first + dy[i];if (x < 0 || N <= x || y < 0 || N <= y) continue;if (chmin(d2[y][x], d2[v.first][v.second] + L[y][x])) {que.push({d2[y][x], {y, x}});}}}if (V - d2[N - 1][N - 1] > 0) cout << "YES\n";else cout << "NO\n";}