結果

問題 No.2366 登校
ユーザー Rainer Evan RuslyRainer Evan Rusly
提出日時 2024-05-05 14:21:43
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 260 ms / 4,000 ms
コード長 2,740 bytes
コンパイル時間 5,650 ms
コンパイル使用メモリ 288,408 KB
実行使用メモリ 23,368 KB
最終ジャッジ日時 2024-11-27 12:21:12
合計ジャッジ時間 6,320 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 89 ms
11,680 KB
testcase_13 AC 88 ms
11,460 KB
testcase_14 AC 85 ms
11,424 KB
testcase_15 AC 89 ms
11,420 KB
testcase_16 AC 86 ms
11,556 KB
testcase_17 AC 85 ms
11,448 KB
testcase_18 AC 85 ms
11,552 KB
testcase_19 AC 87 ms
11,552 KB
testcase_20 AC 85 ms
11,424 KB
testcase_21 AC 85 ms
11,548 KB
testcase_22 AC 64 ms
11,392 KB
testcase_23 AC 53 ms
23,368 KB
testcase_24 AC 53 ms
23,296 KB
testcase_25 AC 260 ms
23,264 KB
testcase_26 AC 256 ms
23,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 80 + 5;
const ll LOG = 31;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'

ll n, m, k, t, tt;
pll a [MAXN][MAXN];
ll dis [MAXN][MAXN][4*MAXN];
bool vis [MAXN][MAXN][4*MAXN];
priority_queue <array <ll, 4>, vector <array <ll, 4> > , greater <array <ll, 4> > > pq;
ll ans = INF;

void dijk(){
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            for(ll u = 0; u <= 2*tt; u++){
                dis[i][j][u] = INF;
                vis[i][j][u] = 0;
            }
        }
    }
    dis[1][1][tt] = 0;
    pq.push({0, 1, 1, tt});
    while(!pq.empty()){
        auto nw = pq.top();
        pq.pop();
        if(vis[nw[1]][nw[2]][nw[3]]) continue;
        vis[nw[1]][nw[2]][nw[3]] = 1;
        // cout << nw[0] << " " << nw[1] << " " << nw[2] << " " << nw[3] << endl;
        if(nw[3]+1 <= 2*tt){
            if(nw[1]+1 <= n && nw[0] < dis[nw[1]+1][nw[2]][nw[3]+1]){
                dis[nw[1]+1][nw[2]][nw[3]+1] = nw[0];
                pq.push({nw[0], nw[1]+1, nw[2], nw[3]+1});
            }
            if(nw[1]-1 >= 1 && nw[0] < dis[nw[1]-1][nw[2]][nw[3]+1]){
                dis[nw[1]-1][nw[2]][nw[3]+1] = nw[0];
                pq.push({nw[0], nw[1]-1, nw[2], nw[3]+1});
            }
            if(nw[2]+1 <= m && nw[0] < dis[nw[1]][nw[2]+1][nw[3]+1]){
                dis[nw[1]][nw[2]+1][nw[3]+1] = nw[0];
                pq.push({nw[0], nw[1], nw[2]+1, nw[3]+1});
            }
            if(nw[2]-1 >= 1 && nw[0] < dis[nw[1]][nw[2]-1][nw[3]+1]){
                dis[nw[1]][nw[2]-1][nw[3]+1] = nw[0];
                pq.push({nw[0], nw[1], nw[2]-1, nw[3]+1});
            }
        }
        if(a[nw[1]][nw[2]].fi != 0){
            ll c = a[nw[1]][nw[2]].fi, d = a[nw[1]][nw[2]].se;
            ll cnt = max(ll(0), nw[3]-c+1);
            if(nw[0]+d < dis[nw[1]][nw[2]][cnt]){
                dis[nw[1]][nw[2]][cnt] = nw[0]+d;
                pq.push({nw[0]+d, nw[1], nw[2], cnt});
            }
        }
    }
}

void solve(){
    cin >> n >> m >> k >> t;
    tt = n+m-2;
    for(ll i = 1; i <= k; i++){
        ll x, y, v, w; cin >> x >> y >> v >> w;
        a[x][y] = {v, w};
    }
    dijk();
    for(ll i = 0; i <= tt + min(t,tt); i++){
        // cout << i-tt << " " << dis[n][m][i] << endl;
        ans = min(ans, dis[n][m][i]);
    }
    if(ans != INF) cout << ans << endl;
    else cout << -1 << endl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // ll t; cin >> t;
    // while(t--){
        solve();
    // }
}
0