結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2020-08-19 19:36:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,179 bytes |
コンパイル時間 | 1,693 ms |
コンパイル使用メモリ | 83,068 KB |
最終ジャッジ日時 | 2025-01-13 03:56:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <vector> #include <tuple> template <class T> std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); } constexpr int INF = 1 << 30; void solve() { int n, k; std::cin >> n >> k; std::vector<std::vector<std::tuple<int, int, int>>> ess(n); { int m; std::cin >> m; std::vector<int> us(m), vs(m), cs(m), ts(m); for (auto& u : us) std::cin >> u; for (auto& v : vs) std::cin >> v; for (auto& c : cs) std::cin >> c; for (auto& t : ts) std::cin >> t; for (int i = 0; i < m; ++i) { ess[--us[i]].emplace_back(--vs[i], cs[i], ts[i]); } } auto dp = vec(n, vec(k + 1, INF)); std::fill(dp[0].begin(), dp[0].end(), 0); for (int u = 0; u < n; ++u) { for (auto [v, c, t] : ess[u]) { for (int x = 0; x + c <= k; ++x) { dp[v][x + c] = std::min(dp[v][x + c], dp[u][x] + t); } } } int ans = dp[n - 1][k]; std::cout << (ans == INF ? -1 : ans) << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }