結果
問題 | No.20 砂漠のオアシス |
ユーザー | Mi_Sawa |
提出日時 | 2015-04-09 00:24:50 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 17 ms / 5,000 ms |
コード長 | 2,217 bytes |
コンパイル時間 | 2,085 ms |
コンパイル使用メモリ | 174,960 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-13 05:05:03 |
合計ジャッジ時間 | 2,242 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>#define all(x) begin(x),end(x)#define rall(x) (x).rbegin(),(x).rend()#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)#define rep(i,n) REP(i,0,n)#define repsz(i,v) rep(i,(v).size())#define aur auto&#define bit(n) (1LL<<(n))#define eb emplace_back#define mt make_tuple#define fst first#define snd secondusing namespace std;typedef long long ll;//#define int long longtemplate<class C>int size(const C &c){ return c.size(); }template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;}template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;}template<typename X> inline bool valid_index(const X &x){ return true; }template<typename V, typename ...Args>inline bool valid_index(const V &v, const int &i, const Args &...args){ return 0<=i and i<v.size() and valid_index(v[i], args...); }int dxy[] = {0, 1, 0, -1, 0};vector<vector<int>> dijk(vector<vector<int>> &b, int sx, int sy){using Elem = tuple<int, int, int>;const int n = size(b);priority_queue<Elem, vector<Elem>, greater<Elem>> pq;vector<vector<int>> d(n, vector<int>(n, numeric_limits<int>::max()));if(!valid_index(b, sx, sy)) return d;pq.emplace(d[sx][sy] = 0, sx, sy);while(!pq.empty()){int c, x, y; tie(c, x, y) = pq.top(); pq.pop();if(c > d[x][y]) continue;rep(dir, 4){int xx = x + dxy[dir], yy = y + dxy[dir+1];if(valid_index(b, xx, yy) and chmin(d[xx][yy], c + b[xx][yy]))pq.emplace(d[xx][yy], xx, yy);}}return d;}bool solve(){int n, v, ox, oy; cin >> n >> v >> oy >> ox; --ox; --oy;vector<vector<int>> b(n, vector<int>(n));rep(i, n) rep(j, n) cin >> b[i][j];auto s = dijk(b, 0, 0), o = dijk(b, ox, oy);string res = "NO";if(s[n-1][n-1] < v) res = "YES";if(valid_index(s, ox, oy) and s[ox][oy] < v and o[n-1][n-1] < 2 * (v - s[ox][oy])) res = "YES";cout << res << endl;return true;}signed main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << std::fixed << std::setprecision(10);solve();return 0;}// vim:set foldmethod=marker commentstring=//%s: