結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2023-11-07 04:08:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,097 bytes |
コンパイル時間 | 1,815 ms |
コンパイル使用メモリ | 201,420 KB |
最終ジャッジ日時 | 2025-02-17 19:55:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 8 WA * 32 |
ソースコード
#include"bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; #define rep(i,m,n) for(ll i=(ll)m;i<(ll)n;i++) #define Endl endl #define pr(i,j) make_pair(i,j) const ll mod = 998244353; const ll inf = 5e18; const ld pi = 3.14159265358979; struct T { ll to; ll time; ll cost; }; int main() { ll n, c, v; cin >> n >> c >> v; vector<vector<ll>>dp(c + 1, vector<ll>(n,inf)); vector<vector<T>> g(n); vector<ll>s(v), t(v), y(v), m(v); rep(i, 0, v) { cin >> s[i]; s[i]--; } rep(i, 0, v) { cin >> t[i]; t[i]--; } rep(i, 0, v) { cin >> y[i]; } rep(i, 0, n) { cin >> m[i]; } rep(i, 0, v) { T in = {}; in.cost = y[i]; in.time = m[i]; in.to = t[i]; g[s[i]].push_back(in); } dp[0][0] = 0; rep(i, 0, c + 1) { rep(j, 0, n) { rep(k, 0, g[j].size()) { if (i + g[j][k].cost <= c) { dp[i + g[j][k].cost][g[j][k].to] = min(dp[i + g[j][k].cost][g[j][k].to], dp[i][j]+g[j][k].time); } } } } ll ans = inf; rep(i, 0, c + 1) { ans = min(ans, dp[i][n - 1]); } if (ans == inf)cout << -1 << endl; else cout << ans << endl; }