結果

問題 No.20 砂漠のオアシス
ユーザー dnishdnish
提出日時 2018-06-23 16:18:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 3,061 bytes
コンパイル時間 1,833 ms
コンパイル使用メモリ 175,976 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-30 18:28:05
合計ジャッジ時間 2,662 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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

#include "bits/stdc++.h"
#define REP(i,n,N) for(ll i=(n); i<(N); i++)
#define RREP(i,n,N) for(ll i=(N-1); i>=n; i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define p(s) cout<<(s)<<endl
#define p2(a,b) cout<<(a)<<" "<<(b)<<endl
#define v2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll inf=1e18;
ll dy[] = {0,1,0,-1};
ll dx[] = {1,0,-1,0};
ll N, V, OY, OX;
ll L[210][210];
ll d1[210][210];//(y,x)
void dijkstra1(){
priority_queue< pair<ll, pair<ll,ll> > > PQ; //(y,x)*(-1)
REP(i,0,N){
REP(j,0,N){
d1[i][j] = inf;
}
}
d1[0][0] = 0;
PQ.push({0, {0,0}});
while(!PQ.empty()){
ll curCost = -PQ.top().first;
ll y = PQ.top().second.first;
ll x = PQ.top().second.second;
PQ.pop();
if(d1[y][x] < curCost){
continue;
}
d1[y][x] = curCost;
REP(k,0,4){
ll ny = y + dy[k];
ll nx = x + dx[k];
if(!CK(ny,0,N) || !CK(nx,0,N)) continue;
ll addCost = L[ny][nx];
if(d1[ny][nx] > curCost + addCost){
d1[ny][nx] = curCost + addCost;
PQ.push({-d1[ny][nx], {ny, nx}});
}
}
}
}
ll d2[210][210]; //
void dijkstra2(){
priority_queue< pair<ll, pair<ll,ll> > > PQ; //(y,x)*(-1)
REP(i,0,N){
REP(j,0,N){
d2[i][j] = inf;
}
}
d2[OY-1][OX-1] = 0;
PQ.push({0, {OY-1,OX-1}});
while(!PQ.empty()){
ll curCost = -PQ.top().first;
ll y = PQ.top().second.first;
ll x = PQ.top().second.second;
PQ.pop();
if(d2[y][x] < curCost){
continue;
}
d2[y][x] = curCost;
REP(k,0,4){
ll ny = y + dy[k];
ll nx = x + dx[k];
if(!CK(ny,0,N) || !CK(nx,0,N)) continue;
ll addCost = L[ny][nx];
if(d2[ny][nx] > curCost + addCost){
d2[ny][nx] = curCost + addCost;
PQ.push({-d2[ny][nx], {ny, nx}});
}
}
}
}
int main(){
while(cin>>N>>V>>OX>>OY){
REP(i,0,N){
REP(j,0,N){
cin>>L[i][j];
}
}
dijkstra1();
//cout<<"d>> "<<d1[OY-1][OX-1]<<endl;
//.
if(d1[N-1][N-1] < V){
cout<<"YES"<<endl;
continue;
}
if((OY == 0 && OX == 0)){
cout<<"NO"<<endl;
continue;
}else if(d1[OY-1][OX-1] >= V){
cout<<"NO"<<endl;
continue;
}else{
//cout<<"d2"<<endl;
dijkstra2();
if(d2[N-1][N-1] < (V-d1[OY-1][OX-1])*2){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0