結果

問題 No.2366 登校
ユーザー logx
提出日時 2021-06-27 18:51:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,873 bytes
コンパイル時間 1,347 ms
コンパイル使用メモリ 93,740 KB
最終ジャッジ日時 2025-01-22 14:43:52
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 1
other AC * 10 RE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<queue>
#include<tuple>

//dp[i][j][k]=(i,j)に時刻kにいる時の疲労度の最小値
//TにN+M-2を加えた上で，k<=2*(N+M-2)のみを考えれば良い

const std::pair<int,int> dij[]={{1,0},{0,1},{-1,0},{0,-1}};
const long long INF=1e18;
using P=std::pair<long long,std::tuple<int,int,int>>;

bool chmin(long long &a,long long b){
    if(a>b)return a=b,true;
    return false;
}

int main(){
    int N,M,K,T;
    std::cin >> N >> M >> K >> T;
    std::vector magic(N,std::vector(M,std::pair<long long,long long>(0,0)));
    for(int i=0;i<K;i++){
        int a,b,c,d;std::cin >> a >> b >> c >> d;
        magic[a-1][b-1]={c,d};
    }

    if(T>=N+M-2){
        std::cout << 0 << '\n';
        return 0;
    }
    T+=N+M-2;
    const int MAX_TIME=(N+M-2)*2;
    std::vector dp(N,std::vector(M,std::vector(MAX_TIME+1,INF)));
    
    dp[0][0][N+M-2]=0;
    std::priority_queue<P,std::vector<P>,std::greater<P>> q;
    q.push({0LL,{0,0,N+M-2}});
    while(!q.empty()){
        auto [dist,p]=q.top();q.pop();
        auto [i,j,nowt]=p;
        if(dp[i][j][nowt] < dist)continue;//これを抜くと落ちるケースは欲しい．
        //魔法を使わない移動 コストは0
        for(auto [di,dj]:dij){
            int ni=i+di, nj=j+dj;
            if(0<=ni && ni<N && 0<=nj && nj<M && chmin(dp[ni][nj][std::min(nowt+1,MAX_TIME)],dist)){
                q.push({dist,{ni,nj,std::min(nowt+1,MAX_TIME)}});
            }
        }
        //魔法を使う移動
        auto [c,d]=magic[i][j];
        if(c==-1)continue;
        int nextt=std::max(nowt-c+1,0LL);
        if(chmin(dp[i][j][nextt],dist+d)){
            q.push({dist+d,{i,j,nextt}});
        }
    }

    long long ans=INF;
    for(int i=0;i<=T;i++){
        chmin(ans,dp[N-1][M-1][i]);
    }
    if(ans==INF)ans=-1;
    std::cout << ans << '\n';
}
0