結果

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

ソースコード

diff # 

#include <cassert>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
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>>;
using Vl = vector<ll>;
using VVl = vector<Vl>;
using VVVl = vector<VVl>;
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;
    VVVl dist((N + M) * 2 - 1, VVl(N, Vl(M, 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();
        }
        //cout << L << ' ' << t - (N + M - 1) << ' ' << u / M << ' ' << u % M << endl;
        int ui = u / M;
        int uj = u % M;
        if (t < (N + M - 1) * 2) {
            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