結果
問題 | 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;}