結果
問題 | No.20 砂漠のオアシス |
ユーザー | mint6421 |
提出日時 | 2019-07-02 15:51:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 34 ms / 5,000 ms |
コード長 | 1,885 bytes |
コンパイル時間 | 1,443 ms |
コンパイル使用メモリ | 164,236 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 11:22:38 |
合計ジャッジ時間 | 2,210 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
コンパイルメッセージ
main.cpp:35:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type] 35 | main(){ | ^~~~
ソースコード
#include<bits/stdc++.h>using namespace std;#define inf 1000000000#define INF 1000000000000000#define ll long long#define ull unsigned long long#define M (int)(1e9+7)#define P pair<int,int>#define PLL pair<ll,ll>#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)#define rep(i,n) FOR(i,0,n)#define rrep(i,n) RFOR(i,n,0)#define all(a) a.begin(),a.end()#define IN(a,n) rep(i,n){ cin>>a[i]; }const int vx[4] = {0,1,0,-1};const int vy[4] = {1,0,-1,0};#define PI 3.14159265#define F first#define S second#define PB push_back#define EB emplace_back#define int llvoid init(){cin.tie(0);ios::sync_with_stdio(false);}int n,v,ox,oy;int a[300][300];main(){cin>>n>>v>>ox>>oy;ox--;oy--;rep(i,n){rep(j,n){cin>>a[i][j];}}int d[300][300];rep(i,n){rep(j,n){d[i][j]=inf;}}d[0][0]=0;queue<P> q;q.push(P(0,0));while(!q.empty()){P p=q.front(); q.pop();rep(k,4){int y=p.F+vy[k],x=p.S+vx[k];if(!(0<=x&&x<n&&0<=y&&y<n)) continue;if(d[p.F][p.S]+a[y][x]<d[y][x]){d[y][x]=d[p.F][p.S]+a[y][x];q.push(P(y,x));}}}if(d[n-1][n-1]<v){cout<<"YES"<<endl;}else{if(ox<0&&oy<0){cout<<"NO"<<endl;}else{int s=v-d[oy][ox];s*=2;rep(i,n){rep(j,n){d[i][j]=inf;}}d[oy][ox]=0;q.push(P(oy,ox));while(!q.empty()){P p=q.front(); q.pop();rep(k,4){int y=p.F+vy[k],x=p.S+vx[k];if(!(0<=x&&x<n&&0<=y&&y<n)) continue;if(d[p.F][p.S]+a[y][x]<d[y][x]){d[y][x]=d[p.F][p.S]+a[y][x];q.push(P(y,x));}}}if(d[n-1][n-1]<s){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}}}