#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class Oasis { public: void solve(void) { int N,V,ox,oy; cin>>N>>V>>ox>>oy; --ox; --oy; vector> field(N,vector(N,0)); REP(i,N) { REP(j,N) cin>>field[i][j]; } const int inf = (1<<30); // V=N*N E=(N-1)*N*4 // 3回 dijkstra をやればよい O(3*E*log(V)) auto calcCost = [&](int sx, int sy, int gx, int gy) { vector> dist(N,vector(N,inf)); typedef tuple P; priority_queue, greater

> que; que.emplace(0,sx,sy); dist[sy][sx] = 0; while (!que.empty()) { int x,y,d; tie(d,x,y) = que.top(); que.pop(); if (dist[y][x] < d) continue; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; REP(d, 4) { int nx = x+dx[d]; int ny = y+dy[d]; if (nx < 0 || ny < 0 || N <= nx || N <= ny) continue; if (dist[y][x] + field[ny][nx] < dist[ny][nx]) { dist[ny][nx] = dist[y][x] + field[ny][nx]; que.emplace(dist[ny][nx],nx,ny); } } } return dist[gy][gx]; }; int v1 = calcCost(0,0,N-1,N-1); if (V > v1) { cout<<"YES"< 0 && (V-v2)*2 > v3) { cout<<"YES"<solve(); delete obj; return 0; } #endif