結果
問題 | 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 |
ソースコード
#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//01BFSd[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;elsecout<<"NO"<<endl;return 0;}