結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2020-03-27 08:40:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 1,002 bytes |
コンパイル時間 | 1,680 ms |
コンパイル使用メモリ | 178,004 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:46:10 |
合計ジャッジ時間 | 2,870 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; int d[50][400]; struct way{int id,re,ti;}; typedef pair<int,int> P; typedef pair<int,P> IP; signed main(){ int n,c,v;cin>>n>>c>>v; vector<int> s(v),t(v),y(v),m(v); for(int i=0;i<v;i++){cin>>s[i];s[i]--;} for(int i=0;i<v;i++){cin>>t[i];t[i]--;} for(int i=0;i<v;i++)cin>>y[i]; for(int i=0;i<v;i++)cin>>m[i]; for(int i=0;i<50;i++)for(int j=0;j<400;j++)d[i][j]=1e9; vector<way> edge[n]; for(int i=0;i<v;i++)edge[s[i]].push_back({t[i],y[i],m[i]}); d[0][c]=0; priority_queue<IP,vector<IP>,greater<IP>> que; que.push(IP(0,P(0,c))); while(que.size()){ IP p=que.top();que.pop(); for(way q:edge[p.second.first]){ int id=q.id; int re=p.second.second-q.re; int ti=p.first+q.ti; if(re>=0){ if(d[id][re]>ti){ d[id][re]=ti; que.push(IP(ti,P(id,re))); } } } } int ans=1e9; for(int j=0;j<=c;j++)if(ans>d[n-1][j])ans=d[n-1][j]; cout<<(ans>1e8?-1:ans)<<endl; }