結果
問題 | No.1638 Robot Maze |
ユーザー |
👑 ![]() |
提出日時 | 2021-08-06 21:57:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,440 bytes |
コンパイル時間 | 1,014 ms |
コンパイル使用メモリ | 85,140 KB |
最終ジャッジ日時 | 2025-01-23 15:16:35 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <iostream> #include <vector> #include <utility> #include <queue> using namespace std; using i32 = int32_t; using i64 = int64_t; #define rep(i,n) for(int i=0; i<(n); i++) const i64 INF = 1001001001001001; struct Edge{ int to; i64 d; }; int H,W; i64 X[6]; int sy,sx,ty,tx; string G; vector<vector<Edge>> E; vector<i64> D; int main(){ cin >> H >> W; rep(t,6) cin >> X[t]; cin >> sy >> sx >> ty >> tx; sy--; sx--; ty--; tx--; rep(y,H){ string g; cin >> g; G += g; } E.resize(H*W); rep(y,H) rep(x,W){ int p = y * W + x; if(y != 0){ E[p].push_back({p-W,X[0]}); E[p-W].push_back({p,X[1]}); } if(x != 0){ E[p].push_back({p-1,X[3]}); E[p-1].push_back({p,X[2]}); } } rep(p,H*W){ for(auto& e : E[p]){ if(G[e.to] == '#') e.d = INF; if(G[e.to] == '@') e.d += X[5]; } } D.assign(H*W,INF); priority_queue<pair<i64,int>> G; G.push({0,sy*W+sx}); D[sy*W+sx] = 0; while(G.size()){ int p = G.top().second; i64 d = -G.top().first; G.pop(); if(D[p] != d) continue; for(auto e : E[p]){ i64 nxd = e.d + d; if(nxd >= D[e.to]) continue; D[e.to] = nxd; G.push({-nxd,e.to}); } } if(D[ty*W+tx] <= X[4]) cout << "Yes\n"; else cout << "No\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;