Submission #22208662

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/












int H, W, A[505][505], B[505][505];
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int vis[505][505];
ll D[505][505];
ll dijk() {
    rep(y, 0, H) rep(x, 0, W) D[y][x] = infl;
    rep(y, 0, H) rep(x, 0, W) vis[y][x] = 0;

    min_priority_queue<pair<ll, int>> que;

    D[0][0] = 0;
    que.push({ 0, 0 });

    while (!que.empty()) {
        auto q = que.top(); que.pop();

        ll cst = q.first;
        int x = q.second % W;
        int y = q.second / W;

        if (x == W - 1 && y == H - 1) return cst;

        if (vis[y][x]) continue;
        vis[y][x] = 1;

        if (x < W - 1) if (chmin(D[y][x + 1], cst + A[y][x])) que.push({ D[y][x + 1], y * W + x + 1 });
        if (0 < x) if (chmin(D[y][x - 1], cst + A[y][x - 1])) que.push({ D[y][x - 1], y * W + x - 1 });
        if (y < H - 1) if (chmin(D[y + 1][x], cst + B[y][x])) que.push({ D[y + 1][x], (y + 1) * W + x });
        rep(dy, 1, y + 1) if (chmin(D[y - dy][x], cst + 1 + dy)) que.push({ D[y - dy][x], (y - dy) * W + x });
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W - 1) cin >> A[y][x];
    rep(y, 0, H - 1) rep(x, 0, W) cin >> B[y][x];

    cout << dijk() << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll dijk()’:
./Main.cpp:43:39: warning: control reaches end of non-void function [-Wreturn-type]
   43 |     min_priority_queue<pair<ll, int>> que;
      |                                       ^~~

Judge Result