結果
問題 | No.2328 Build Walls |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:19:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 316 ms / 3,000 ms |
コード長 | 2,553 bytes |
コンパイル時間 | 2,402 ms |
コンパイル使用メモリ | 227,168 KB |
最終ジャッジ日時 | 2025-02-13 11:15:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;const unsigned long long INF = 1002003004005006007;template<class T>std::vector<unsigned long long> dijkstra(std::vector<std::vector<std::pair<int,T>>>& to, int s=0) {struct QueElem {int v;unsigned long long c;bool operator<(const QueElem a) const {return c > a.c;}QueElem(int v, unsigned long long c): v(v), c(c) {}};std::priority_queue<QueElem> q;std::vector<unsigned long long> dist(to.size(), INF);dist[s] = 0;q.emplace(s, 0);while(!q.empty()) {QueElem qe = q.top(); q.pop();int u = qe.v;unsigned long long c = qe.c;if (c > dist[u]) continue;for(auto vc: to[u]) {int v = vc.first;unsigned long long nc = c + vc.second;if (nc < dist[v]) {dist[v] = nc;q.emplace(v, nc);}}}return dist;}} int main() {ios::sync_with_stdio(false);cin.tie(0);int h, w;cin >> h >> w;VVI a(h, VI(w, -1));rep(i, h) if (1 <= i && i < h - 1) rep(j, w) cin >> a[i][j];int s = h * w, t = s + 1;vector<vector<P>> to(t + 1);rep(i, h) if (a[i][0] != -1) {int v = i * w;to[s].emplace_back(v, a[i][0]);}rep(i, h) if (a[i][w - 1] != -1) {int v = i * w + w - 1;to[v].emplace_back(t, 0);}rep(i, h) rep(j, w) if (a[i][j] != -1) {int u = i * w + j;for(int di = -1; di <= 1; di++) {for(int dj = -1; dj <= 1; dj++) {if (di == 0 && dj == 0) continue;int ni = i + di, nj = j + dj;if (!(0 <= ni && ni < h && 0 <= nj && nj < w) || a[ni][nj] == -1) continue;int v = ni * w + nj;to[u].emplace_back(v, a[ni][nj]);}}}ll ans = dijkstra(to, s)[t];if (ans == INF) ans = -1;cout << ans << '\n';}