結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2015-08-27 13:32:30 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,186 bytes |
コンパイル時間 | 752 ms |
コンパイル使用メモリ | 74,484 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:16:58 |
合計ジャッジ時間 | 1,993 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <numeric> #include <algorithm> #include <string> #include <vector> #include <functional> #include <cmath> #include <queue> #define rep(i, a) FOR(i, 0, a) #define FOR(i, a, b) for(int i = a; i < b; ++i) typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> P; struct edge{ int to, time, cost; }; const int max = 51; const int inf = (int)1e+9; int n, c; std::vector<edge> node[max]; int dp[55][301]; int main(){ int v; int s[1501], t[1501], y[1501], m[1501]; std::cin >> n >> c >> v; rep(i, v)std::cin >> s[i]; rep(i, v)std::cin >> t[i]; rep(i, v)std::cin >> y[i]; rep(i, v)std::cin >> m[i]; rep(i, v){ edge a; a.to = t[i] - 1; a.cost = y[i]; a.time = m[i]; node[s[i] - 1].push_back(a); } rep(i, 55)rep(j, 301)dp[i][j] = inf; dp[0][0] = 0; rep(i, n)rep(j, 301){ if (dp[i][j] == inf)continue; rep(k, node[i].size()){ int to = node[i][k].to, cost = j + node[i][k].cost, time = dp[i][j] + node[i][k].time; if (cost < 301)dp[to][cost] = std::min(dp[to][cost], time); } } int ans = *std::min_element(dp[n - 1], dp[n - 1] + c + 1); std::cout << (ans == inf ? -1 : ans) << std::endl; return 0; }