結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー A8pf
提出日時 2019-07-01 13:04:52
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 24 ms / 5,000 ms
コード長 2,545 bytes
コンパイル時間 1,699 ms
コンパイル使用メモリ 180,348 KB
実行使用メモリ 6,784 KB
最終ジャッジ日時 2024-07-08 13:07:40
合計ジャッジ時間 2,648 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> P;
class Edge
{
	public:
	int to,cost;
	Edge(int t,int c)
	{
		to=t;cost=c;
	}
};

vector<Edge> g[40000]; //(i,j)=i*200+jでエンコード
int d[40000]; //スタート地点から各点への距離
int m[200][200]; //グリッド

//n頂点グラフのsからtへの01BFS最短距離
int bfs(int s,int t,int n)
{
	deque<P> q;
	fill(d,d+n,1e8-1); //距離がllなら1e17-1
	//01BFS
	d[s]=0;
	q.push_back(P(d[s],s));
	while(!q.empty())
	{
		P p=q[0]; //先頭を取り出す
		q.pop_front();
		for(int i=0;i<g[p.second].size();i++)
		{
			Edge e=g[p.second][i];
			if(d[e.to]==1e8-1)//終了条件！！！
			{
				d[e.to]=p.first+1;
				q.push_back(P(d[e.to],e.to));
			}
		}
	}
	//デバッグ用各グリッドへの距離の出力(h,wが別途必要）
	/*
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
			cerr<<(d[i*50+j]==1e8-1 ? -1 : d[i*50+j])<<" ";
		cerr<<endl;
	}*/
	return d[t];
}

//n頂点のダイクストラ
int dijk(int s,int t,int n)
{
	priority_queue<P,vector<P>,greater<P>> q;
	fill(d,d+n,1e8-1);
	d[s]=0;
	q.push(P(d[s],s));
	while(!q.empty())
	{
		P p=q.top();q.pop();
		if(p.first>d[p.second])
			continue;
		for(int i=0;i<g[p.second].size();i++)
		{
			Edge e=g[p.second][i];
			if(d[e.to]>p.first+e.cost)
			{
				d[e.to]=p.first+e.cost;
				q.push(P(d[e.to],e.to));
			}
		}
	}
	return d[t];
}

int main()
{
	int n,v,ox,oy;
	cin>>n>>v>>ox>>oy;
	ox--;oy--;
	int s=0; //スタート地点(0,0)
	int t=200*(n-1)+(n-1); //ゴール地点(n-1,n-1)
	int o=200*ox+oy;
	int dx[4]={1,0,-1,0};
	int dy[4]={0,-1,0,1};//右上左下
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			cin>>m[j][i]; //iとjを入力に応じて入れ替える
	}
	/* スタートとゴールを0indexedに戻すのを忘れない！！！ */
	//グラフの作成
	//この場合x方向が行となる。つまり下が右
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			//4方向すべて調べる
			for(int k=0;k<4;k++)
			{
				int nx=i+dx[k];
				int ny=j+dy[k];
				if(nx>-1 && nx<n && ny>-1 && ny<n)
				{
					//反対辺はどうせ後で調べるのでやらなくてよい
					g[i*200+j].push_back(Edge(nx*200+ny,m[nx][ny]));
				}
			}
		}
	}
	int st=dijk(s,t,40000); //st間の距離
	int so=1e8-1;
	int ot=1e8-1;
	//オアシスが存在するならオアシス経由のルートを計算
	if(o>0)
	{
		so=d[o];
		ot=dijk(o,t,40000);
	}
	cerr<<st<<" "<<so<<" "<<ot<<endl;
	if(st<v || ot<(v-so)*2)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	return 0;
}
0