結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2020-08-26 23:48:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 759 bytes |
コンパイル時間 | 1,811 ms |
コンパイル使用メモリ | 172,408 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 14:19:32 |
合計ジャッジ時間 | 2,987 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 WA * 3 |
ソースコード
#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 dp[50]; int ans=INF; int N,C,V; void dfs(int v,int c,int t){ if(dp[v]<t)return; dp[v] = t; for (auto &&i : G[v]){ if(c<i.cost)continue; dfs(i.end,c-i.cost,t+i.time); } } int main() { 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,N)dp[i]=INF;dp[0]=0; 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(dp[N-1]==INF)cout<<-1<<endl; else cout<<dp[N-1]<<endl; }