結果

問題 No.2366 登校
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2021-06-28 22:57:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,444 bytes
コンパイル時間 1,975 ms
コンパイル使用メモリ 184,744 KB
実行使用メモリ 14,052 KB
最終ジャッジ日時 2023-09-22 05:08:29
合計ジャッジ時間 12,358 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_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();
        while (!pque.empty() && L != dist[t][u / M][u % M]) {
            tie(L, t, u) = pque.top();
        }
        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