結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー char134217728
提出日時 2017-08-25 10:28:57
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 25 ms / 5,000 ms
コード長 3,437 bytes
コンパイル時間 2,156 ms
コンパイル使用メモリ 197,496 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-06-28 10:37:34
合計ジャッジ時間 3,147 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:57:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   57 | main(){
      | ^~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) a.begin(),a.end()
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double eps = 1e-10;


struct Dijk{
  // solve(s, g) or solve(s).
  // show d and p.
  typedef pair<ll,int> pli;
  int n;
  vector<vpll>E;
  vl d;
  vi p;
  void init(const vector<vpll>&e){n=sz(e);E=e;FOR(i,0,n)sort(rng(E[i]));d.resize(n);p.resize(n);}
  void o(int S,int G){FOR(i,0,n){d[i]=(i==S)?0:linf;p[i]=-1;}priority_queue<pli,vector<pli>,greater<pli>>Q;Q.push(pll(0,S));pli t;vector<bool>F;FOR(i,0,n)F.pb(0);ll f;int c=0,s;while(!Q.empty()){t=Q.top();Q.pop();f=t.fi;s=t.se;if(F[s])continue;F[s]=1;c++;if(c==n||s==G)break;each(itr,E[s]){ll ff=itr->fi,ss=itr->se;if((!F[ff])&&(f+ss<d[ff])){d[ff]=f+ss;p[ff]=s;Q.push(pll(f+ss,ff));}}}}
  ll solve(int s,int g){o(s,g);return d[g];}
  void solve(int s){o(s,-1);}
};

ll n, v, s, g, L[100][100], d;
vector<vpll> E;
int pt[10000], tn, vn;
set<pii> ss[10000];
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> v;
  cin >> s >> d;
  s = (d - 1) * 100 + s - 1;
  cin >> g >> d;
  g = (d - 1) * 100 + g - 1;
  FOR(j, 0, n)FOR(i, 0, n)cin >> L[i][j];
  E.resize(10000);
  FOR(i, 0, n)FOR(j, 0, n){
    ll _i, _j;
    if(i > 0){
      _i = i-1;
      _j = j;
      E[j*100+i].pb(pll(_j*100+_i, L[_i][_j]));
    }
    if(i < n-1){
      _i = i+1;
      _j = j;
      E[j*100+i].pb(pll(_j*100+_i, L[_i][_j]));
    }
    if(j > 0){
      _i = i;
      _j = j-1;
      E[j*100+i].pb(pll(_j*100+_i, L[_i][_j]));
    }
    if(j < n-1){
      _i = i;
      _j = j+1;
      E[j*100+i].pb(pll(_j*100+_i, L[_i][_j]));
    }
  }
  Dijk dij;
  dij.init(E);
  d = dij.solve(s, g);
  if(d >= v){
    cout << -1 << endl;
    return 0;
  }
  int mt = 0, co = g;
  while(dij.p[co] != -1){
    co = dij.p[co];
    mt++;
  }
  FOR(i, 0, 10000){
    pt[i] = iinf;
  }
  typedef pair<pii, int> tii;
  priority_queue<tii, vector<tii>, greater<tii> > que;
  que.push(tii(pii(0, 0), s));
  pt[s] = 0;
  ss[s].insert(pii(0,0));
  tii t;
  while(true){
    t = que.top();
    que.pop();
    if(t.se == g){
      cout << t.fi.fi << endl;
      return 0;
    }
    each(itr, E[t.se]){
      tn = t.fi.fi + 1;
      vn = t.fi.se + itr->se;
      if((vn < v)&&(pt[itr->fi]>vn)&&ss[itr->fi].find(pii(tn, vn))==ss[itr->fi].end()){
        mins(pt[itr->fi], vn);
        ss[itr->fi].insert(pii(tn, vn));
        que.push(tii(pii(tn, vn), itr->fi));
      }
    }
  }
}
0