結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー Rumain831
提出日時 2026-07-30 04:24:20
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 631 ms / 5,000 ms
+ 967µs
コード長 977 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,762 ms
コンパイル使用メモリ 206,064 KB
実行使用メモリ 398,336 KB
最終ジャッジ日時 2026-07-30 04:24:36
合計ジャッジ時間 8,058 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
using qu = tuple<int, int, int, int>;

//Tags: ダイクストラ法

int main(void){
  int n, v, sx, sy, gx, gy; 
  cin >> n >> v >> sx >> sy >> gx >> gy; sx--, sy--, gx--, gy--;
  vector l(n, vector<int>(n));
  vector dist(n, vector(n, vector<int>(v+1, 1e9)));
  for(auto&x:l)for(auto&y:x) cin >> y;
  queue<qu> pri;
  pri.emplace(v, 0, sy, sx);
  dist[sy][sx][v]=0;
  int di[4]={-1, 0, 1, 0};
  int dj[4]={0, 1, 0, -1};
  while(pri.size()){
    auto [hp, d, i, j]=pri.front(); pri.pop();
    if(dist[i][j][hp]!=d) continue;
    if(i==gy&&j==gx){
      cout << d << endl; return 0;
    }
    for(int k=0; k<4; k++){
      int ni=i+di[k], nj=j+dj[k];
      if(ni<0||nj<0||ni>=n||nj>=n) continue;
      int nv=hp-l[ni][nj];
      if(nv<=0) continue;
      if(dist[ni][nj][nv]>d+1){
        dist[ni][nj][nv]=d+1;
        pri.emplace(nv, d+1, ni, nj);
      }
    }
  }
  cout << -1 << endl;
  return 0; 
}
0