結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2020-08-26 00:02:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 749 bytes |
コンパイル時間 | 1,919 ms |
コンパイル使用メモリ | 172,656 KB |
実行使用メモリ | 13,640 KB |
最終ジャッジ日時 | 2024-11-06 11:54:44 |
合計ジャッジ時間 | 12,453 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 TLE * 1 -- * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i = 0; i < n; ++i) using ll = long long; const int INF=1e9; struct edge{int end,cost,time;}; vector<vector<edge>>G(50); int ans=INF; int n,c,v; void dfs(int v,int c,int t){ if(v==n-1)ans=min(ans,t); for (auto &&i : G[v]){ if(c<i.cost)continue; dfs(i.end,c-i.cost,t+i.time); } } int main() { ios::sync_with_stdio(false); cin.tie(0); 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]; rep(i,v){ edge e; e.end=T[i]-1;e.cost=Y[i];e.time=M[i]; G[S[i]-1].push_back(e); } dfs(0,c,0); if(ans==INF)cout<<-1<<endl; else cout<<ans<<endl; }