結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2020-05-31 13:08:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,566 bytes |
コンパイル時間 | 1,756 ms |
コンパイル使用メモリ | 181,092 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:48:38 |
合計ジャッジ時間 | 2,964 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(i,n) for (int i = 0; i < (n); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const ll INF=1LL<<60; const int inf=(1<<30)-1; const int mod=1e9+7; int dx[8]={1,0,-1,0,-1,-1,1,1}; int dy[8]={0,1,0,-1,-1,1,-1,1}; int main(){ cin.tie(0); ios::sync_with_stdio(false); int n,c,v;cin >> n >> c >> v; vector<vector<pair<ll,pair<ll,ll>>>> e(n); 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]; rep(i,v){ s[i]--,t[i]--; e[s[i]].push_back({t[i],{y[i],m[i]}}); } priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> pq; vector<vector<ll>> d(n,vector<ll>(c+1,INF)); d[0][c]=0; pq.push({0,{0,c}}); while(!pq.empty()){ auto p=pq.top(); pq.pop(); ll u=p.first,v=p.second.first,w=p.second.second; if(u>d[v][w]){ continue; } for(auto x:e[v]){ ll i=x.first,j=x.second.first,k=x.second.second; if(w-j>=0){ if(chmin(d[i][w-j],d[v][w]+k)){ pq.push({d[i][w-j],{i,w-j}}); } } } } ll ans=INF; for(int i=0;i<=c;i++){ chmin(ans,d[n-1][i]); } cout << (ans==INF?-1:ans) << endl; }