結果
問題 | No.2328 Build Walls |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:47:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 771 ms / 3,000 ms |
コード長 | 1,911 bytes |
コンパイル時間 | 954 ms |
コンパイル使用メモリ | 78,980 KB |
最終ジャッジ日時 | 2025-02-13 12:04:12 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <iostream> #include <vector> #include <queue> using namespace std; typedef long long ll; typedef pair<ll,int> pll; vector<pll> G[4000100]; //weight,vertex priority_queue<pll,vector<pll>,greater<pll>> que; ll d[4000100],INF = 100000000000000000; void add_edge(int from,int to,ll weight){ G[from].push_back({weight,to}); // if(to==13) cout << from << " " << to << " " << weight << endl; } void dijkstra(int s){ que.push({0,s}); while(que.size()){ pll p = que.top(); que.pop(); ll dis = p.first,pos = p.second; if(d[pos]!=INF) continue; d[pos] = dis; for(auto e:G[pos]){ if(d[e.second]==INF) que.push({dis + e.first,e.second}); } } } int a[1010][1010]; int dx[8] = {1,1,0,-1,-1,-1,0,1}; int dy[8] = {0,1,1,1,0,-1,-1,-1}; bool ch(int h,int w,int nx,int ny){ if(nx<0 || nx>=h || ny<0 || ny>=w || a[nx][ny]==-1) return false; return true; } int mp(int w,int nx,int ny){ return w*nx + ny; } int main(){ int i,j,k,h,w; cin >> h >> w; for(i=0;i<h - 2;i++){ for(j=0;j<w;j++){ cin >> a[i][j]; } } for(i=0;i<h - 2;i++){ for(j=0;j<w;j++){ if(a[i][j]==-1) continue; for(k=0;k<8;k++){ int nx = i + dx[k],ny = j + dy[k]; if(!ch(h - 2,w,nx,ny)) continue; add_edge(mp(w,i,j),mp(w,nx,ny),a[i][j]); } } } int s = (h - 2)*w; int t = (h - 2)*w + 1; for(i=0;i<=t;i++) d[i] = INF; for(i=0;i<h - 2;i++){ if(a[i][0]!=-1) add_edge(s,mp(w,i,0),0); if(a[i][w - 1]!=-1) add_edge(mp(w,i,w - 1),t,a[i][w - 1]); } dijkstra(s); if(d[t]!=INF) cout << d[t] << "\n"; else cout << -1 << "\n"; // for(i=0;i<(h - 2)*w;i++){ // cout << d[i] << " "; // if(i%w==w - 1) cout << "\n"; // } // cout << d[s] << " " << d[t] << endl; }