結果
問題 | No.2328 Build Walls |
ユーザー |
![]() |
提出日時 | 2023-05-28 15:39:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 156 ms / 3,000 ms |
コード長 | 1,604 bytes |
コンパイル時間 | 1,290 ms |
コンパイル使用メモリ | 116,360 KB |
最終ジャッジ日時 | 2025-02-13 13:42:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
// I SELL YOU...!#include<iostream>#include<vector>#include<algorithm>#include<functional>#include<queue>#include<chrono>#include<iomanip>#include<map>#include<set>using namespace std;using ll = long long;using P = pair<ll,ll>;using TP = tuple<ll,ll,ll>;void init_io(){cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(18);}const ll INF = 1e12;signed main(){init_io();ll h,w;cin >> h >> w;vector<vector<ll>> a(h, vector<ll>(w, -1));vector<vector<ll>> dp(h, vector<ll>(w, INF));priority_queue<TP, vector<TP>, greater<TP>> que;for(int i=1;i<h-1;i++){for(int j=0;j<w;j++) {cin >> a[i][j];if (j==0 && a[i][j] != -1) {dp[i][j] = a[i][j];que.push(TP(a[i][j], i, j));}}}while(!que.empty()) {auto [v, i, j] = que.top(); que.pop();if (dp[i][j] < v) continue;ll nx[] = {i-1, i, i+1, i-1, i+1, i-1, i, i+1};ll ny[] = {j-1, j-1, j-1, j, j, j+1, j+1, j+1};for (int t=0;t<8;t++) {ll ni = nx[t];ll nj = ny[t];if (ni>0 && ni <h-1 && nj >= 0 && nj < w && a[ni][nj] != -1) {ll nv = v + a[ni][nj];if (dp[ni][nj] > nv) {que.push(TP(nv, ni, nj));dp[ni][nj] = nv;}}}}ll ans = INF;for (int i=0;i<h;i++) {ans = min(ans, dp[i][w-1]);}/*cout << endl;for (int i=0;i<h;i++) {for(int j=0;j<w;j++) {if (dp[i][j] == INF) dp[i][j] = -1;cout << dp[i][j] <<" ";}cout << endl;}cout << endl;*/if (ans == INF) ans = -1;cout << ans << endl;}