結果

問題 No.2366 登校
コンテスト
ユーザー vjudge1
提出日時 2024-05-05 13:19:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,594 bytes
コンパイル時間 1,876 ms
コンパイル使用メモリ 204,068 KB
最終ジャッジ日時 2025-02-21 11:01:28
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16 WA * 9
権限があれば一括ダウンロードができます

ソースコード

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;
pll a [MAXN][MAXN];
ll dis [MAXN][MAXN][2*MAXN];
bool vis [MAXN][MAXN][2*MAXN];
priority_queue <array <ll, 4>, vector <array <ll, 4> > , greater <array <ll, 4> > > pq;

void dijk(){
    for(ll i = 1; i <= n; i++){
        for(ll j = 1; j <= m; j++){
            for(ll u = 0; u <= n+m-2; u++){
                dis[i][j][u] = INF;
                vis[i][j][u] = 0;
            }
        }
    }
    dis[1][1][0] = 0;
    pq.push({0, 1, 1, 0});
    while(!pq.empty()){
        auto nw = pq.top();
        // cout << nw[0] << " " << nw[1] << " " << nw[2] << " " << nw[3] << endl;
        pq.pop();
        if(vis[nw[1]][nw[2]][nw[3]]) continue;
        vis[nw[1]][nw[2]][nw[3]] = 1;
        if(nw[3]+1 <= n+m-2){
            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;
    for(ll i = 1; i <= k; i++){
        ll x, y, v, w; cin >> x >> y >> v >> w;
        a[x][y] = {v, w};
    }
    dijk();
    if(dis[n][m][min(t,n+m-2)] != INF) cout << dis[n][m][t] << 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