結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2017-03-14 02:23:29 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 2,425 bytes |
コンパイル時間 | 641 ms |
コンパイル使用メモリ | 63,656 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:29:08 |
合計ジャッジ時間 | 1,818 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <cassert> #include <iostream> #include <vector> #include <algorithm> #include <utility> #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--) #define rep(i, n) for (int i = 0; i < (n); i++) #define rep1(i, n) for (int i = 1; i <= (n); i++) #define rrep(i, n) for (int i = (n)-1; i >= 0; i--) #define pb push_back #define mp make_pair #define fst first #define snd second #define show(x) cout << #x << " = " << x << endl #define chmin(x, y) x = min(x, y) #define chmax(x, y) x = max(x, y) #define pii pair<int, int> #define vi vector<int> using namespace std; template <class S, class T> ostream& operator<<(ostream& o, const pair<S, T>& p) { return o << "(" << p.first << "," << p.second << ")"; } template <class T> ostream& operator<<(ostream& o, const vector<T>& vc) { o << "sz = " << vc.size() << endl << "["; for (const T& v : vc) o << v << ","; o << "]"; return o; } typedef long long ll; #define NMAX 51 #define MAX 1501 #define CMAX 301 #define inf 1e9 + 7 int N, C, V; int S[MAX]; int T[MAX]; int Y[MAX]; int M[MAX]; int data[NMAX][CMAX]; struct edge { int to; int cost; int tim; }; vector<edge> edges[NMAX]; int main() { cin >> N >> C >> V; rep(i, V) { cin >> S[i]; } rep(i, V) { cin >> T[i]; } rep(i, V) { cin >> Y[i]; } rep(i, V) { cin >> M[i]; } rep(i, V) { edges[S[i]].pb(edge{T[i], Y[i], M[i]}); } rep(i, N + 1) { rep(j, C + 1) { data[i][j] = inf; } } rep(i, C + 1) { data[1][i] = 0; } rep1(i, N) { rep(c, C + 1) { if (data[i][c] < inf) { for (const auto& j : edges[i]) { int to = j.to; int cost = j.cost; int tim = j.tim; if (c + cost <= C) { chmin(data[to][c + cost], data[i][c] + tim); } } } } } if (data[N][C] >= inf) { cout << -1 << endl; } else { // int minc = inf; // rep(i, C + 1) // { // chmin(minc, data[N][i]); // } // cout << data[N][C] << " " << minc << endl; cout << data[N][C] << endl; } return 0; }