結果

問題 No.2366 登校
ユーザー logxlogx
提出日時 2021-06-27 18:51:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 1,873 bytes
コンパイル時間 961 ms
コンパイル使用メモリ 98,008 KB
実行使用メモリ 19,812 KB
最終ジャッジ日時 2023-09-22 05:07:52
合計ジャッジ時間 5,095 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 RE -
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 RE -
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 AC 2 ms
4,380 KB
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 AC 7 ms
4,376 KB
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
権限があれば一括ダウンロードができます

ソースコード

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