結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2014-11-17 19:57:03 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,175 bytes |
コンパイル時間 | 1,515 ms |
コンパイル使用メモリ | 80,416 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:07:16 |
合計ジャッジ時間 | 1,944 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> using namespace std; int main(){ int n; cin >> n; int c; cin >> c; int v; cin >> v; vector<vector<int> > edge(n); vector<int> s(v); for(int i=0; i<v; i++){ cin >> s[i]; s[i]--; } vector<int> t(v); for(int i=0; i<v; i++){ cin >> t[i]; t[i]--; } vector<int> y(v); for(int i=0; i<v; i++) cin >> y[i]; vector<int> m(v); for(int i=0; i<v; i++) cin >> m[i]; for(int i=0; i<v; i++){ edge[ s[i] ].push_back( i ); } const int INF = 1e9; vector< vector<int> > dp(n, vector<int>(c+1, INF)); fill(dp[0].begin(), dp[0].end(), 0); for(int i=0; i<n; i++){ for(int j=0; j<edge[i].size(); j++){ int e = edge[i][j]; for(int k=0; k<=c; k++){ if( k - y[e] < 0 ) continue; dp[ t[e] ][ k-y[e] ] = min( dp[ t[e] ][ k-y[e] ], dp[i][k] + m[e]); } } } int ans = *min_element(dp[n-1].begin(), dp[n-1].end()); if(ans >= INF){ cout << -1 << endl; }else{ cout << ans << endl; } return 0; }