結果

問題 No.20 砂漠のオアシス
ユーザー char134217728char134217728
提出日時 2017-08-24 21:45:25
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 38 ms / 5,000 ms
コード長 2,749 bytes
コンパイル時間 2,533 ms
コンパイル使用メモリ 171,652 KB
実行使用メモリ 11,924 KB
最終ジャッジ日時 2023-08-05 17:17:54
合計ジャッジ時間 4,283 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,508 KB
testcase_01 AC 4 ms
5,584 KB
testcase_02 AC 4 ms
5,584 KB
testcase_03 AC 5 ms
5,844 KB
testcase_04 AC 6 ms
5,900 KB
testcase_05 AC 31 ms
11,016 KB
testcase_06 AC 33 ms
11,924 KB
testcase_07 AC 33 ms
11,784 KB
testcase_08 AC 38 ms
11,812 KB
testcase_09 AC 34 ms
11,768 KB
testcase_10 AC 4 ms
5,416 KB
testcase_11 AC 5 ms
5,412 KB
testcase_12 AC 6 ms
5,656 KB
testcase_13 AC 5 ms
5,804 KB
testcase_14 AC 7 ms
6,036 KB
testcase_15 AC 6 ms
6,040 KB
testcase_16 AC 10 ms
6,800 KB
testcase_17 AC 9 ms
6,688 KB
testcase_18 AC 10 ms
6,676 KB
testcase_19 AC 11 ms
6,832 KB
testcase_20 AC 5 ms
5,596 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:53:6: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
 main(){
      ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) a.begin(),a.end()
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return (int)p;}

const int iinf = 1e9;
const ll linf = 4e18;
const int mod = 1e9+7;
const double eps = 1e-10;

struct Dijk{
  // solve(s, g) or solve(s).
  // show d and p.
  typedef pair<ll,int> pli;
  int n;
  vector<vpll>E;
  vl d;
  vi p;
  void init(const vector<vpll>&e){n=sz(e);E=e;FOR(i,0,n)sort(rng(E[i]));d.resize(n);p.resize(n);}
  void o(int S,int G){FOR(i,0,n){d[i]=(i==S)?0:linf;p[i]=-1;}priority_queue<pli,vector<pli>,greater<pli>>Q;Q.push(pll(0,S));pli t;vector<bool>F;FOR(i,0,n)F.pb(0);ll f;int c=0,s;while(!Q.empty()){t=Q.top();Q.pop();f=t.fi;s=t.se;if(F[s])continue;F[s]=1;c++;if(c==n||s==G)break;each(itr,E[s]){ll ff=itr->fi,ss=itr->se;if((!F[ff])&&(f+ss<d[ff])){d[ff]=f+itr->se;p[ff]=s;Q.push(pll(f+ss,ff));}}}}
  ll solve(int s,int g){o(s,g);return d[g];}
  void solve(int s){o(s,-1);}
};

int n, v, x[2], L[200][200];
vector<vpll> E;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> v >> x[0] >> x[1];
  x[0]--;
  x[1]--;
  int o = x[1]*200 + x[0];
  E.resize(40000);
  FOR(i, 0, n)FOR(j, 0, n)cin >> L[j][i];
  FOR(_y, 0, n)FOR(_x, 0, n){
    int __x, __y, id = _y*200+_x;
    if(_x>0){
      __x = _x - 1;
      __y = _y;
      E[id].pb(pll(__y*200+__x, L[__x][__y]));
    }
    if(_y>0){
      __x = _x;
      __y = _y - 1;
      E[id].pb(pll(__y*200+__x, L[__x][__y]));
    }
    if(_x<n-1){
      __x = _x + 1;
      __y = _y;
      E[id].pb(pll(__y*200+__x, L[__x][__y]));
    }
    if(_y<n-1){
      __x = _x;
      __y = _y + 1;
      E[id].pb(pll(__y*200+__x, L[__x][__y]));
    }
  }
  Dijk dij;
  dij.init(E);
  ll d1 = dij.solve(0, (n-1)*201);
  ll d2 = linf;
  if(o >= 0) d2 = 2 * dij.solve(0, o) + dij.solve(o, (n-1)*201);
  cout << ((d1 < v || d2 < v * 2) ? "YES" : "NO") << endl;
}
0