結果
問題 | No.20 砂漠のオアシス |
ユーザー | SSRS |
提出日時 | 2020-11-08 23:52:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 5,000 ms |
コード長 | 2,147 bytes |
コンパイル時間 | 2,016 ms |
コンパイル使用メモリ | 182,564 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 15:47:46 |
合計ジャッジ時間 | 2,692 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 100000;vector<int> dy = {1, 0, -1, 0};vector<int> dx = {0, 1, 0, -1};int main(){int N, V, Ox, Oy;cin >> N >> V >> Ox >> Oy;Ox--;Oy--;vector<vector<int>> L(N, vector<int>(N));for (int i = 0; i < N; i++){for (int j = 0; j < N; j++){cin >> L[i][j];}}vector<vector<int>> S1(N, vector<int>(N, INF));priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq1;pq1.push(make_tuple(0, 0, 0));while (!pq1.empty()){int c = get<0>(pq1.top());int y = get<1>(pq1.top());int x = get<2>(pq1.top());pq1.pop();if (S1[y][x] == INF){S1[y][x] = c;for (int i = 0; i < 4; i++){int y2 = y + dy[i];int x2 = x + dx[i];if (0 <= y2 && y2 < N && 0 <= x2 && x2 < N){if (S1[y2][x2] == INF){pq1.push(make_tuple(c + L[y2][x2], y2, x2));}}}}}if (Ox == -1 && Oy == -1){if (S1[N - 1][N - 1] < V){cout << "YES" << endl;} else {cout << "NO" << endl;}} else {if (S1[N - 1][N - 1] < V){cout << "YES" << endl;} else if (S1[Oy][Ox] >= V){cout << "NO" << endl;} else {vector<vector<int>> S2(N, vector<int>(N, INF));priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq2;pq2.push(make_tuple(0, Oy, Ox));while (!pq2.empty()){int c = get<0>(pq2.top());int y = get<1>(pq2.top());int x = get<2>(pq2.top());pq2.pop();if (S2[y][x] == INF){S2[y][x] = c;for (int i = 0; i < 4; i++){int y2 = y + dy[i];int x2 = x + dx[i];if (0 <= y2 && y2 < N && 0 <= x2 && x2 < N){if (S2[y2][x2] == INF){pq2.push(make_tuple(c + L[y2][x2], y2, x2));}}}}}if (S2[N - 1][N - 1] < (V - S1[Oy][Ox]) * 2){cout << "YES" << endl;} else {cout << "NO" << endl;}}}}