結果

問題 No.2366 登校
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2021-06-28 22:58:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 256 ms / 4,000 ms
コード長 2,488 bytes
コンパイル時間 1,660 ms
コンパイル使用メモリ 186,024 KB
実行使用メモリ 33,792 KB
最終ジャッジ日時 2023-09-03 02:46:41
合計ジャッジ時間 4,060 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,384 KB
testcase_07 AC 2 ms
5,504 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 77 ms
22,352 KB
testcase_13 AC 75 ms
22,936 KB
testcase_14 AC 77 ms
22,416 KB
testcase_15 AC 80 ms
24,064 KB
testcase_16 AC 79 ms
22,716 KB
testcase_17 AC 80 ms
22,640 KB
testcase_18 AC 81 ms
22,996 KB
testcase_19 AC 78 ms
22,316 KB
testcase_20 AC 78 ms
22,684 KB
testcase_21 AC 72 ms
22,604 KB
testcase_22 AC 63 ms
22,688 KB
testcase_23 AC 49 ms
33,776 KB
testcase_24 AC 47 ms
33,588 KB
testcase_25 AC 253 ms
33,792 KB
testcase_26 AC 256 ms
33,676 KB
権限があれば一括ダウンロードができます

ソースコード

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