結果

問題 No.20 砂漠のオアシス
ユーザー SSRSSSRS
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0