結果

問題 No.2366 登校
ユーザー Carpenters-Cat
提出日時 2021-06-28 22:58:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 334 ms / 4,000 ms
コード長 2,488 bytes
コンパイル時間 1,858 ms
コンパイル使用メモリ 180,128 KB
実行使用メモリ 41,728 KB
最終ジャッジ日時 2025-06-20 10:23:54
合計ジャッジ時間 5,386 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cassert>
#include <queue>
using namespace std;
using ll = long long;
using P = pair<ll, int>;
using PP = tuple<ll, int, int>;
using PQ = priority_queue<PP, vector<PP>, greater<PP>>;
int main () {
    int N, M, K, T;
    cin >> N >> M >> K >> T;
    assert(1 <= N && N <= 100);
    assert(1 <= M && M <= 100);
    assert(0 <= K && K <= N * M - 2);
    assert(1 <= T && T <= 1000000000);
    if (T > N + M - 1) {
        cout << 0 << endl;
        return 0;
    }
    vector<vector<int>> C(N, vector<int>(M, 0));
    vector<vector<ll>> D(N, vector<ll>(M, 0));
    for (int i = 0; i < K; i ++) {
        int a, b, c;
        ll d;
        cin >> a >> b >> c >> d;
        assert(1 <= a && a <= N);
        assert(1 <= b && b <= M);
        assert(a + b != 2 && a + b != N + M);
        assert(1 <= c && c <= 1000000000);
        assert(1 <= d && d <= 1000000000);
        assert(C[a - 1][b - 1] == 0);
        C[a - 1][b - 1] = c;
        D[a - 1][b - 1] = d;
    }
    ll INF = (ll)1e17;
    ll dist[402][110][110];
    for (int i = 0; i <= (N + M - 1) * 2; i ++) {
        for (int j = 0; j < N; j ++) {
            for (int k = 0; k < M; k ++) {
                dist[i][j][k] = INF;
            }
        }
    }
    dist[N + M - 1][0][0] = 0;
    PQ pque;
    pque.push(make_tuple(0, N + M - 1, 0));
    int mon[] = {0, 1, 0, -1};
    int mom[] = {1, 0, -1, 0};
    while(!pque.empty()) {
        ll L;
        int t, u;
        tie(L, t, u) = pque.top();
        pque.pop();
        while (!pque.empty() && L != dist[t][u / M][u % M]) {
            tie(L, t, u) = pque.top();
            pque.pop();
        }
        int ui = u / M;
        int uj = u % M;
        for (int p = 0; p < 4; p ++) {
            int vi = ui + mon[p];
            int vj = uj + mom[p];
            if (vi < 0 || vi >= N || vj < 0 || vj >= M) {
                continue;
            }
            if (dist[t + 1][vi][vj] > L) {
                dist[t + 1][vi][vj] = L;
                pque.push(make_tuple(L, t + 1, vi * M + vj));
            }
        }
        if (C[ui][uj] > 1 && dist[max(0, t - C[ui][uj] + 1)][ui][uj] > L + D[ui][uj]) {
            dist[max(0, t - C[ui][uj] + 1)][ui][uj] = L + D[ui][uj];
            pque.push(make_tuple(L + D[ui][uj], max(0, t - C[ui][uj] + 1), u));
        }
    }
    ll ans = INF;
    for (int i = 0; i <= T + N + M - 1; i ++) {
        ans = min(ans, dist[i][N - 1][M - 1]);
    }
    cout << (ans == INF ? -1 : ans) << endl;
}
0