結果

問題 No.2366 登校
コンテスト
ユーザー hitonanode
提出日時 2025-08-06 00:15:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 347 ms / 4,000 ms
コード長 2,269 bytes
コンパイル時間 1,235 ms
コンパイル使用メモリ 105,356 KB
実行使用メモリ 19,760 KB
最終ジャッジ日時 2025-08-06 00:15:59
合計ジャッジ時間 4,445 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using lint = long long;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }
const std::vector<std::pair<int, int>> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {0, 0}};

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, M, K, T;
    cin >> N >> M >> K >> T;

    if (T >= (N - 1) + (M - 1)) {
        puts("0");
        return 0;
    }

    vector<int> C(N * M);
    vector<int> D(N * M);

    const int B = N + M;
    const int W = B * 2 + 1;

    auto fij = [&](int i, int j) { return i * M + j; };
    auto isin = [&](int i, int j, int t) {
        return 0 <= i and i < N and 0 <= j and j < M and - B <= t and t <= B;
    };
    auto f = [&](int i, int j, int t) {
        assert(isin(i, j, t));
        return (i * M + j) * W + (t + B);
    };

    REP(k, K) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        --a, --b;
        C.at(fij(a, b)) = c - 1;
        D.at(fij(a, b)) = d;
        // cerr << "k" << a << ' ' << b << ' ' << c << ' ' << d << '\n';
    }

    const int sz = N * M * W;
    constexpr lint inf = 1LL << 60;
    vector<lint> dp(sz, inf);
    dp.at(f(0, 0, 0)) = 0;

    using S = tuple<lint, int, int, int>;
    priority_queue<S, vector<S>, greater<S>> pq;
    pq.emplace(0, 0, 0, 0);

    while (!pq.empty()) {
        auto [dpnow, i, j, t] = pq.top();
        // cerr << dpnow << ' ' << i << ' ' << j << ' ' << t << '\n';
        pq.pop();
        if (dpnow > dp.at(f(i, j, t))) continue;

        for (auto [di, dj] : grid_dxs) {
            const int ni = i + di, nj = j + dj, nt = t + 1;
            if (!isin(ni, nj, nt)) continue;
            if (chmin(dp.at(f(ni, nj, nt)), dpnow)) pq.emplace(dpnow, ni, nj, nt);
        }

        if (const int tnxt = max(t - C.at(fij(i, j)), -B); isin(i, j, tnxt)) {
            if (chmin(dp.at(f(i, j, tnxt)), dpnow + D.at(fij(i, j)))) {
                pq.emplace(dp.at(f(i, j, tnxt)), i, j, tnxt);
            }
        }
    }

    lint ret = dp.at(f(N - 1, M - 1, T));
    cout << (ret < inf ? ret : -1) << '\n';
}
0