結果
問題 | No.2328 Build Walls |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:19:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 477 ms / 3,000 ms |
コード長 | 1,428 bytes |
コンパイル時間 | 4,737 ms |
コンパイル使用メモリ | 266,168 KB |
最終ジャッジ日時 | 2025-02-13 11:14:12 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;typedef modint998244353 mint;typedef long long ll;int main(){int h, w; cin >> h >> w;vector<vector<int>> a(h-2, vector<int>(w));for (int i=0; i<h-2; i++){for (int j=0; j<w; j++){cin >> a[i][j];}}vector<vector<vector<pair<int,int>>>> ikeru(h-2, vector<vector<pair<int,int>>>(w, vector<pair<int,int>>(0)));vector<pair<int,int>> go = {pair(0,-1), pair(0,1),pair(-1,-1), pair(-1,0), pair(-1,1),pair(1,-1), pair(1,0), pair(1,1)};for (int i=0; i<h-2; i++){for (int j=0; j<w; j++){for (auto[xx,yy]:go){int x = i+xx;int y = j+yy;if (0<=x && x<h-2 && 0<=y && y<w && a[x][y] != -1){ikeru[i][j].push_back(pair(x,y));}}}}vector<vector<int>> d(h-2, vector<int>(w, 1e9));priority_queue<tuple<int,int,int>> pq;for (int i=0; i<h-2; i++){if (a[i][0] != -1){pq.push(make_tuple(-a[i][0], i, 0));d[i][0] = a[i][0];}}while(!pq.empty()){int t = -get<0>(pq.top());int i = get<1>(pq.top());int j = get<2>(pq.top());pq.pop();if (t > d[i][j]) continue;for (auto [x, y]: ikeru[i][j]){if (t + a[x][y] < d[x][y]){d[x][y] = t + a[x][y];pq.push(make_tuple(-d[x][y], x, y));}}}int ans = 1e9;for (int i=0; i<h-2; i++){ans = min(ans, d[i][w-1]);}if (ans == 1e9) cout << -1 << endl;else cout << ans << endl;}