結果

問題 No.34 砂漠の行商人
ユーザー GOTKAKO
提出日時 2025-05-22 18:40:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,245 ms / 5,000 ms
コード長 1,411 bytes
コンパイル時間 2,555 ms
コンパイル使用メモリ 218,860 KB
実行使用メモリ 84,048 KB
最終ジャッジ日時 2025-05-22 18:40:47
合計ジャッジ時間 16,734 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,V,sx,sy,gx,gy; cin >> N >> V >> sx >> sy >> gx >> gy;
    swap(sx,sy); swap(gx,gy);
    V = min(V,2000); sx--; sy--; gx--; gy--;
    vector<vector<int>> L(N,vector<int>(N));
    for(auto &h : L) for(auto &w : h) cin >> w;

    vector dist(N,vector(N,vector<int>(V+1,-1)));
    queue<tuple<int,int,int>> Q; Q.push({sx,sy,V});
    dist.at(sx).at(sy).at(V) = 0;
    vector<pair<int,int>> dxy = {{-1,0},{0,1},{1,0},{0,-1}};
    vector Dxy(N,vector<vector<pair<int,int>>>(N));
    for(int i=0; i<N; i++) for(int k=0; k<N; k++){
        for(auto [dx,dy] : dxy){
            int ii = i+dx,kk = k+dy;
            if(min(ii,kk) < 0 || max(ii,kk) >= N) continue;
            Dxy.at(i).at(k).push_back({ii,kk});
        }
    }
    while(Q.size()){
        auto [x,y,v] = Q.front(); Q.pop();
        int d = dist.at(x).at(y).at(v);
        for(auto [nx,ny] : Dxy.at(x).at(y)){
            int nv = v-L.at(nx).at(ny);
            if(nv <= 0) continue;
            if(dist.at(nx).at(ny).at(nv) != -1) continue;
            dist.at(nx).at(ny).at(nv) = d+1; Q.push({nx,ny,nv});
        }
    }
    int answer = 1001001001;
    for(int i=1; i<=V; i++) if(dist.at(gx).at(gy).at(i) != -1) answer = min(answer,dist.at(gx).at(gy).at(i));
    if(answer > 1e9) answer = -1;
    cout << answer << endl;
}
0