結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2015-10-28 11:19:15 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 1,329 bytes |
コンパイル時間 | 1,442 ms |
コンパイル使用メモリ | 167,448 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:17:50 |
合計ジャッジ時間 | 2,517 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define lp(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) lp(i, 0, n) #define rlp(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--) #define rrep(i, n) rlp(i, 0, n) #define mp make_pair #define mt make_tuple #define pb push_back #define eb emplace_back #define all(c) begin(c), end(c) typedef long long ll; typedef unsigned long long ull; const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1}; const int MOD = 1e9 + 7; const int INF = 1 << 28; const ll INFLL = 1ll << 60; template<typename T> inline void unique(T &c){ sort(all(c)); c.erase(unique(all(c)), end(c)); } typedef tuple<int, int, int> Tp; int n, c, v; int s[1510], t[1510], y[1510], m[1510]; int dp[60][310]; vector<Tp> g[60]; int main() { cin >> n >> c >> v; rep(i, v) cin >> s[i], s[i]--; rep(i, v) cin >> t[i], t[i]--; rep(i, v) cin >> y[i]; rep(i, v) cin >> m[i]; rep(i, v) g[s[i]].eb(t[i], y[i], m[i]); fill(*dp, dp[60], 1 << 28); dp[0][0] = 0; rep(i, n) rep(j, c) for (auto &e : g[i]){ int to, cost, dist; tie(to, cost, dist) = e; if (j + cost > c) continue; dp[to][j + cost] = min(dp[to][j + cost], dp[i][j] + dist); } int res = *min_element(dp[n - 1], dp[n - 1] + c + 1); if (res == (1 << 28)) cout << "-1\n"; else cout << res << endl; }