結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー spade630
提出日時 2015-11-04 17:06:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 1,865 bytes
コンパイル時間 789 ms
コンパイル使用メモリ 80,404 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-13 05:30:30
合計ジャッジ時間 1,620 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:72:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 |                 scanf("%d", &maze[i][j]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <ctime>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FFOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
#define RREP(i,b) FFOR(i,1,b)
#define PB push_back
#define F first
#define S second
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef LL ut;
typedef long double ld;
typedef pair<ut,ut> pr;
typedef vector<pr> Vpr;
typedef vector<ut> VI;
typedef pair<ut,pr> ppr;
typedef priority_queue<pr,Vpr, greater<pr> > PQ;
const int SIZE=1e+5 + 1;
const ut INF=1<<29;
const ld eps=1e-6;
const LL mod=1e+6 + 3;

int N, V, ox, oy;
int maze[256][256];
int d[256][256];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool check(int x, int y){
	return x >= 0 && x < N && y >= 0 && y < N;
}

void dijkstra(int sx, int sy){
	REP(i,N)REP(j,N)
		d[i][j] = INF;
	priority_queue<ppr, vector<ppr>, greater<ppr>> que;
	que.push(ppr(0, pr(sx, sy)));
	d[sy][sx] = 0;
	
	while(!que.empty()){
		ppr p = que.top(); que.pop();
		int x = p.S.F, y = p.S.S;
		if(d[y][x] < p.F)
			continue;
		REP(i,4){
			int nx = x + dx[i], ny = y + dy[i];
			if(check(nx, ny)){
				if(d[ny][nx] > d[y][x] + maze[ny][nx]){
					d[ny][nx] = d[y][x] + maze[ny][nx];
					que.push(ppr(d[ny][nx], pr(nx, ny)));
				}
			}
		}
	}	
}

int main() {
	cin >> N >> V >> ox >> oy;
	REP(i,N)REP(j,N){
		scanf("%d", &maze[i][j]);
	}
	dijkstra(0, 0);
	if(V - d[N - 1][N - 1] > 0){
		cout << "YES" << endl;
	}
	else if(ox + oy == 0 || V - d[oy - 1][ox - 1] <= 0){
		cout << "NO" << endl;
	}
	else{
		V = (V - d[oy - 1][ox - 1]) * 2;
		dijkstra(ox - 1, oy - 1);
		if(V - d[N - 1][N - 1] <= 0){
			cout << "NO" << endl;
		}
		else{
			cout << "YES" << endl;
		}
	}
 	return 0;
}
0