結果
問題 | No.1638 Robot Maze |
ユーザー |
![]() |
提出日時 | 2021-08-06 21:50:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,784 bytes |
コンパイル時間 | 3,076 ms |
コンパイル使用メモリ | 186,672 KB |
最終ジャッジ日時 | 2025-01-23 15:07:08 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; int main() { int h, w; cin>>h>>w; ll c[4]; int dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, 1, -1}; for(int i=0; i<4; i++) cin>>c[i]; ll k, p; cin>>k>>p; ll d[101][101]; int xs, ys, xt, yt; cin>>xs>>ys>>xt>>yt; xs--; ys--; xt--; yt--; string s[101]; for(int i=0; i<h; i++) cin>>s[i]; const ll INF=1e18; for(int i=0; i<h; i++) for(int j=0; j<w; j++) d[i][j]=INF; d[xs][ys]=0; using Pl=pair<ll, P>; priority_queue<Pl, vector<Pl>, greater<Pl>> que; que.push({0, {xs, ys}}); while(!que.empty()){ auto q=que.top(); que.pop(); int x=q.second.first, y=q.second.second; if(q.first>d[x][y]) continue; for(int i=0; i<4; i++){ int x1=x+dx[i], y1=y+dy[i]; if(x1<0 || x1>=h || y1<0 || y1>=w) continue; if(s[x1][y1]=='#') continue; ll cost=c[i]; if(s[x1][y1]=='@') cost+=p; if(d[x1][y1]>d[x][y]+cost){ d[x1][y1]=d[x][y]+cost; que.push({d[x1][y1], {x1, y1}}); } } } //cout<<d[xt][yt]<<endl; if(d[xt][yt]<=k) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }