結果

問題 No.20 砂漠のオアシス
ユーザー ttkkggww
提出日時 2022-03-21 14:22:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 37 ms / 5,000 ms
コード長 1,450 bytes
コンパイル時間 5,061 ms
コンパイル使用メモリ 258,672 KB
最終ジャッジ日時 2025-01-28 10:54:03
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using ll = long long;
int n,v,ox,oy;
vector<vector<int>> L;
int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
using P = pair<int,int>;

void solve(){
	vector<vector<P>> G(n*n);
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			int st = i*n+j;
			for(int k = 0;k<4;k++){
				if(i+dx[k]<0||i+dx[k]>=n||j+dy[k]<0||j+dy[k]>=n)continue;
				int ed = (i+dx[k])*n + (j+dy[k]);
				G[st].push_back(P(ed,L[i+dx[k]][j+dy[k]]));
			}
		}
	}
	auto dijkstra = [&](int st,int ed){
		priority_queue<P,vector<P>,greater<>>PQ;
		vector<int> dist(n*n,INT_MAX);
		PQ.push(P(0,st));
		dist[st] = 0;
		while(PQ.size()){
			auto [curCost,cur] = PQ.top();
			PQ.pop();
			if(curCost!=dist[cur])continue;
			for(auto &[to,toCost]:G[cur]){
				if(dist[to]>curCost+toCost){
					dist[to] = curCost+toCost;
					PQ.push(P(dist[to],to));
				}
			}
		}
		return dist[ed];
	};
	bool is = false;
	if(dijkstra(0,n*n-1)<v){
		is = true;
	}
	if(ox==-1&&oy==-1){
		if(is)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		return;
	}
	if((v-dijkstra(0,ox*n+oy))*2>dijkstra(ox*n+oy,n*n-1)){
		is = true;
	}
	if(is)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> n >> v >> ox >> oy;
	L = vector<vector<int>>(n,vector<int>(n));
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++)cin >> L[i][j];
	}
	ox--;
	oy--;
	swap(ox,oy);
	solve();
}
0