結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー pessimist
提出日時 2025-06-14 21:01:31
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 322 ms / 5,000 ms
コード長 1,434 bytes
コンパイル時間 5,046 ms
コンパイル使用メモリ 210,512 KB
実行使用メモリ 106,124 KB
最終ジャッジ日時 2025-06-14 21:01:39
合計ジャッジ時間 6,878 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int L[111][111];
int dist[111][111][2222];
int q[2220222], q_st, q_size;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); 
    int di[4]={-1,1,0,0};
    int dj[4]={0,0,-1,1};

    int N,V; cin>>N>>V; --V;
    int SX,SY; cin>>SY>>SX; --SY,--SX;
    int GX, GY; cin>>GY>>GX; --GY,--GX;
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            cin>>L[i][j];
        }
    }

    if(V>=2*N*9){
        cout<<abs(SX-GX)+abs(SY-GY)<<endl;
        return 0;
    }

    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            for(int k=0;k<=V;++k){
                dist[i][j][k]=-1;
            }
        }
    }

    dist[SX][SY][V]=0;
    int q_st=0, q_size=0;
    q[q_st+q_size++]=(SX*N+SY)*(V+1)+V;
    
    int res=-1;
    while(q_size){
        auto m=q[q_st++]; q_size--;
        auto k=m%(V+1); m/=(V+1);
        int i=m/N, j=m%N;
        for(int d=0;d<4;++d){
            int ni=i+di[d];
            int nj=j+dj[d];
            if(ni<0||nj<0||ni>=N||nj>=N) continue;
            int nk=k-L[ni][nj];
            if(nk<0) continue;
            if(dist[ni][nj][nk] >= 0) continue;

            int nn=(ni*N+nj)*(V+1)+nk;
            dist[ni][nj][nk]=dist[i][j][k]+1;
            if(ni==GX&&nj==GY){res=dist[ni][nj][nk]; break;}
            q[q_st+q_size++]=nn;
        }
        if(res>=0) break;
    }
    cout<<res<<endl;
    return 0;
}
0