結果
問題 | No.20 砂漠のオアシス |
ユーザー | togari_takamoto |
提出日時 | 2016-02-25 22:26:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 32 ms / 5,000 ms |
コード長 | 1,816 bytes |
コンパイル時間 | 1,523 ms |
コンパイル使用メモリ | 174,188 KB |
実行使用メモリ | 8,320 KB |
最終ジャッジ日時 | 2024-10-13 05:33:03 |
合計ジャッジ時間 | 2,333 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vb = vector<bool>; using vd = vector<double>; using vl = vector<ll>; using vvi = vector<vi>; using vvb = vector<vb>; using vvd = vector<vd>; using vvl = vector<vl>; #define REP(i,n) for(ll i=0; i<(n); ++i) #define FOR(i,b,n) for(ll i=(b); i<(n); ++i) #define ALL(v) (v).begin(), (v).end() #define TEN(x) ((ll)1e##x) typedef ll Id; typedef ll Distance; #define INF_DIST numeric_limits<Distance>::max() struct Edge{Id to; Distance cost;}; typedef vector<vector<Edge>> Graph; vector<Distance> dijkstra(Id s, const Graph & g){ vector<Distance> d(g.size(), INF_DIST); d[s] = 0; typedef pair<Distance, Id> P; priority_queue<P, vector<P>, greater<P>> que; que.push(P(0, s)); while(!que.empty()){ P p = que.top(); que.pop(); Id v = p.second; if(d[v] < p.first) continue; for (Edge e : g[v]) if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } return d; } ll dx[] = { -1, 0, 1, 0 }; ll dy[] = { 0, -1, 0, 1 }; bool contain(ll x, ll max_x) { return 0 <= x && x < max_x; } int main() { ll n, v, ox, oy; cin >> n >> v >> ox >> oy; vvl field(n, vl(n)); REP(y, n) REP(x, n) cin >> field[y][x]; Graph g(n*n); REP(y, n) REP(x, n) { REP(d, 4) if (contain(y + dy[d], n) && contain(x + dx[d], n)) { g[y*n + x].push_back({ (y + dy[d])*n + (x + dx[d]), field[y + dy[d]][x + dx[d]] }); } } auto dist = dijkstra(0, g); if (dist[n*n - 1] < v) { cout << "YES" << endl; }else if (ox != 0) { v -= dist[(oy-1)*n + ox-1]; v *= 2; dist = dijkstra((oy-1)*n + ox-1, g); cout << (dist[n*n - 1] < v ? "YES" : "NO") << endl; } else { cout << "NO" << endl; } return 0; }