#747366 (C++17) No.20 砂漠のオアシス

• 問題: No.20 砂漠のオアシス
• ユーザー: ttkkggww
• 提出日時: 2022-03-21 14:22:06
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 28 ms / 5,000 ms
• コード長: 1,450 bytes
• コンパイル時間: 4,784 ms
• コンパイル使用メモリ: 260,224 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2024-04-17 07:26:19
• 合計ジャッジ時間: 5,288 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	23 ms; 6,144 KB
testcase_06	AC	28 ms; 6,400 KB
testcase_07	AC	28 ms; 6,400 KB
testcase_08	AC	27 ms; 6,400 KB
testcase_09	AC	28 ms; 6,400 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	3 ms; 5,376 KB
testcase_14	AC	4 ms; 5,376 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	6 ms; 5,376 KB
testcase_17	AC	5 ms; 5,376 KB
testcase_18	AC	6 ms; 5,376 KB
testcase_19	AC	6 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB

ソースコード

#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();
}