結果

問題 No.1 道のショートカット
コンテスト
ユーザー char134217728
提出日時 2017-08-26 13:26:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,991 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,071 ms
コンパイル使用メモリ 197,924 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 16:33:17
合計ジャッジ時間 3,243 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
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, C, V, S[1500], T[1500], Y[1500], M[1500];
int DP[50][301];
vector<vpll> E;
typedef pair<pii, int> tii;
vector<vector<pair<int, pii> > >F;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> C >> V;
  FOR(i, 0, V)cin >> S[i];
  FOR(i, 0, V)cin >> T[i];
  FOR(i, 0, V)cin >> Y[i];
  FOR(i, 0, V)cin >> M[i];
  E.resize(n);
  F.resize(n);
  FOR(i, 0, V){
    E[S[i]-1].pb(pll(T[i]-1, Y[i]));
    F[S[i]-1].pb(pair<int, pii>(T[i]-1, pii(M[i], Y[i])));
  }
  Dijk dij;
  dij.init(E);
  ll d = dij.solve(0, n-1);
  if(d > C){
    cout << -1 << endl;
    return 0;
  }
  FOR(i, 1, n){
    FOR(j, 0, 301){
      DP[i][j] = iinf;
    }
  }
  priority_queue<tii, vector<tii>, greater<tii> > que;
  que.push(tii(pii(0, 0), 0));
  tii t;
  int tn, vn;
  while(true){
    t = que.top();
    que.pop();
    if(t.se == n-1){
      cout << t.fi.fi << endl;
      return 0;
    }
    each(itr, F[t.se]){
      tn = t.fi.fi + itr->se.fi;
      vn = t.fi.se + itr->se.se;
      if((vn <= C)&&(DP[itr->fi][vn] > tn)){
        FOR(i, vn, 301)mins(DP[itr->fi][i], tn);
        que.push(tii(pii(tn, vn), itr->fi));
      }
    }
  }
}
0