結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2018-01-06 14:10:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,069 bytes |
コンパイル時間 | 1,646 ms |
コンパイル使用メモリ | 171,848 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:34:25 |
合計ジャッジ時間 | 2,730 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> #define FI(i,a,b) for(int i=(a);i<=(b);i++) #define FD(i,b,a) for(int i=(b);i>=(a);i--) #define len(a) int((a).size()) using namespace std; using LL = long long; using PII = pair<int, int>; const int N = 55, V = 1505; struct Edge { int u, v, y, m; }; int n, c, v; int S[V], T[V], Y[V], M[V]; int F[N][305]; vector<int> G[N]; vector<Edge> E; int main() { scanf("%d%d%d", &n, &c, &v); FI(i,1,v) scanf("%d", &S[i]); FI(i,1,v) scanf("%d", &T[i]); FI(i,1,v) scanf("%d", &Y[i]); FI(i,1,v) scanf("%d", &M[i]); FI(i,1,v) { E.push_back({S[i], T[i], Y[i], M[i]}); G[S[i]].push_back(E.size() - 1); } memset(F, 10, sizeof F); FI(i,0,c) F[1][i] = 0; FI(u,1,n) { for (auto i: G[u]) { Edge e = E[i]; FI(j,e.y,c) { F[e.v][j] = min(F[e.v][j], F[u][j-e.y] + e.m); } } } int ans = *min_element(F[n], F[n] + c + 1); if (ans >= 10000000) return !printf("-1\n"); printf("%d\n", *min_element(F[n], F[n] + c + 1)); }