結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2019-09-01 12:50:22 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,439 bytes |
コンパイル時間 | 953 ms |
コンパイル使用メモリ | 101,228 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:41:32 |
合計ジャッジ時間 | 2,182 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <string> #include <iomanip> #include <map> #include <set> #include <cmath> #include <cstdio> using namespace std; #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++) #define All(v) (v).begin(),(v).end() typedef long long ll; using tp = tuple<int,int,int>; int main(){ int N,C,V; cin >> N >> C >> V; vector<int> S(V),T(V),Y(V),M(V); rep(i,V)cin >> S[i]; rep(i,V)cin >> T[i]; rep(i,V)cin >> Y[i]; rep(i,V)cin >> M[i]; vector<vector<tp> >G(N); rep(i,V){ G[S[i]-1].push_back(make_tuple(T[i]-1,Y[i],M[i])); } const int INF =1<<30; priority_queue<tp,vector<tp>,greater<tp> > que; vector<vector<ll> > d(N,vector<ll>(C+1,INF));//d:=(time,cost) d[0][0]=0; que.push(make_tuple(0,0,0)); while(!que.empty()){ tp a = que.top();que.pop(); int time,v,cost; tie(time,cost,v)=a; if(d[v][cost]<time)continue; for(tp e:G[v]){ int nv,adc,adt; tie(nv,adc,adt)= e; if(d[nv][cost+adc]<=d[v][cost]+adt||cost+adc>C)continue; d[nv][cost+adc]=d[v][cost]+adt; que.push(make_tuple(d[nv][cost+adc],cost+adc,nv)); } } ll res = INF; rep(i,C+1)res = min(res,d[N-1][i]); cout << (res==INF?-1:res) << endl; return 0; }