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