結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2014-12-03 21:28:46 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,401 bytes |
コンパイル時間 | 723 ms |
コンパイル使用メモリ | 78,940 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:07:29 |
合計ジャッジ時間 | 1,942 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <sstream> #include <cstdio> #include <cmath> #include <algorithm> #include <functional> using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i,n) for (int i = 0; i < (n); i++) #define REPS(i,n) for (int i = 0; i <= (n); i++) #define FOR(i,s,n) for (int i = (s); i < (n); i++) #define FORS(i,s,n) for (int i = (s); i <= (n); i++) const int E = 1500; int n, c, v, s[E], t[E], y[E], m[E]; struct edge { int to, cost, dist; edge(int to, int cost, int dist) : to(to), cost(cost), dist(dist) {} }; typedef vector<vector<edge> > graph; graph G; const int N = 50; const int C = 300; const int inf = int(1e9); int dp[N][C + 1]; int main() { int n,c,v; cin >> n >> c >> 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]; G.assign(n, vector<edge>()); REP(i, v) G[s[i]-1].emplace_back(t[i]-1,y[i],m[i]); fill((int*)dp, (int*)dp+N*(C+1), inf); dp[0][0] = 0; REP(i, n) for(const auto &e : G[i]) REPS(k, c) { if(e.cost+k > c) continue; dp[e.to][e.cost+k] = min(dp[e.to][e.cost+k], dp[i][k]+e.dist); } int ans = *min_element(dp[n-1],dp[n-1]+c+1); cout << (ans == inf ? -1 : ans) << endl; return 0; }