結果
問題 | 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,vertexpriority_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;}