結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2018-11-02 14:47:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,296 bytes |
コンパイル時間 | 1,939 ms |
コンパイル使用メモリ | 209,892 KB |
最終ジャッジ日時 | 2025-01-06 15:26:10 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} //INSERT ABOVE HERE signed main(){ Int n,c,w; cin>>n>>c>>w; using T = tuple<Int, Int, Int>; vector<vector<T> > G(n); { vector<Int> s(w),t(w),y(w),m(w); for(Int i=0;i<w;i++) cin>>s[i]; for(Int i=0;i<w;i++) cin>>t[i]; for(Int i=0;i<w;i++) cin>>y[i]; for(Int i=0;i<w;i++) cin>>m[i]; for(Int i=0;i<w;i++){ s[i]--;t[i]--; G[s[i]].emplace_back(t[i],y[i],m[i]); } } const Int INF = 1e8; vector<vector<Int> > dp(n,vector<Int>(c+1,INF)); priority_queue<T, vector<T>, greater<T> > pq; dp[0][0]=0; pq.emplace(dp[0][0],0,0); while(!pq.empty()){ Int v,x,d; tie(d,v,x)=pq.top();pq.pop(); //cout<<d<<" "<<v<<" "<<x<<":"<<dp[v][x]<<endl; if(dp[v][x]<d) continue; for(T e:G[v]){ Int u,y,m; tie(u,y,m)=e; Int nx=x+y,nd=d+m; if(nx>c) continue; if(dp[u][nx]>nd){ dp[u][nx]=nd; pq.emplace(dp[u][nx],u,nx); } } } Int ans=INF; for(Int x=0;x<=c;x++) chmin(ans,dp[n-1][x]); if(ans>=INF) ans=-1; cout<<ans<<endl; return 0; }