結果
問題 | No.2328 Build Walls |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:13:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 229 ms / 3,000 ms |
コード長 | 1,339 bytes |
コンパイル時間 | 3,887 ms |
コンパイル使用メモリ | 259,836 KB |
最終ジャッジ日時 | 2025-02-13 11:06:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint998244353;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 4000000000000000001int main(){int H,W;cin>>H>>W;vector a(H,vector<int>(W,-1));rep(i,H){if(i==0||i==H-1)continue;rep(j,W){cin>>a[i][j];}}rep(i,H){a[i].insert(a[i].begin(),0);a[i].push_back(0);}vector dis(H,vector<long long>(W+2,Inf64));priority_queue<pair<long long,pair<int,int>>,vector<pair<long long,pair<int,int>>>,greater<pair<long long,pair<int,int>>>> Q;rep(i,H){dis[i][0] = 0;Q.emplace(0,make_pair(i,0));}while(Q.size()>0){long long D = Q.top().first;int x = Q.top().second.first;int y = Q.top().second.second;Q.pop();if(dis[x][y]!=D)continue;for(int i=-1;i<=1;i++){for(int j=-1;j<=1;j++){int xx = x+i,yy = y+j;if(xx<0||xx>=H||yy<0||yy>=W+2)continue;//cout<<xx<<','<<yy<<endl;if(a[xx][yy] == -1)continue;long long nD = D + a[xx][yy];if(dis[xx][yy]>nD){dis[xx][yy] = nD;Q.emplace(nD,make_pair(xx,yy));}}}}/*rep(i,H){rep(j,W+2){cout<<dis[i][j]<<',';}cout<<endl;}*/long long ans = dis[0].back();if(ans==Inf64)ans = -1;cout<<ans<<endl;return 0;}