結果
問題 | No.20 砂漠のオアシス |
ユーザー | kyuridenamida |
提出日時 | 2016-02-10 22:14:25 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 25 ms / 5,000 ms |
コード長 | 1,323 bytes |
コンパイル時間 | 1,623 ms |
コンパイル使用メモリ | 164,876 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-13 05:32:34 |
合計ジャッジ時間 | 2,545 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; int done[200][200]; int L[200][200]; int dx[] = {-1,0,1,0}; int dy[] = {0,1,0,-1}; struct NODE{ int x,y,c; }; bool operator < (const NODE &a,const NODE &b){ return a.c > b.c; } int main(){ int N,V,Ox,Oy; cin >> N >> V >> Ox >> Oy; --Ox,--Oy; for(int i = 0 ; i < N ; i++) for(int j = 0 ; j < N ; j++) cin >> L[i][j]; priority_queue<NODE> Q; int V2 = -1; Q.push({0,0,0}); while( Q.size() ){ auto q = Q.top(); Q.pop(); if( done[q.y][q.x]++ ) continue; if( q.c >= V ) continue; if( q.y == N - 1 && q.x == N - 1 ){ cout << "YES" << endl; return 0; } if( q.y == Oy && q.x == Ox ){ V2 = max(V2,2*(V - q.c)); } for(int i = 0 ; i < 4 ; i++){ int tx = q.x + dx[i]; int ty = q.y + dy[i]; if( tx < 0 || tx >= N || ty >= N || ty < 0 ) continue; Q.push({tx,ty,q.c+L[ty][tx]}); } } memset(done,0,sizeof(done)); Q.push({Ox,Oy,0}); while( Q.size() ){ auto q = Q.top(); Q.pop(); if( done[q.y][q.x]++ ) continue; if( q.c >= V2 ) continue; if( q.y == N - 1 && q.x == N - 1 ){ cout << "YES" << endl; return 0; } for(int i = 0 ; i < 4 ; i++){ int tx = q.x + dx[i]; int ty = q.y + dy[i]; if( tx < 0 || tx >= N || ty >= N || ty < 0 ) continue; Q.push({tx,ty,q.c+L[ty][tx]}); } } cout << "NO" << endl; }