結果
問題 |
No.1 道のショートカット
|
ユーザー |
![]() |
提出日時 | 2019-11-29 18:21:35 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,024 bytes |
コンパイル時間 | 711 ms |
コンパイル使用メモリ | 72,836 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-08 05:18:46 |
合計ジャッジ時間 | 1,924 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 4 |
other | WA * 40 |
ソースコード
#include <set> #include <cstdio> #include <vector> #include <iostream> #include <utility> #include <queue> #include <algorithm> #define fir first #define sec second #define get(n) scanf("%d",&n); #define gets(s) string s;cin >> (s); #define All(s) (c).begin(), (c).end() #define chmin(x, y) x = min(x, y); #define chmax(x, y) x = max(x, y); #define rep(i, j) for (int (i)=0;(i)<(j);(i)++) #define repk(i, j, k) for(int (i)=(j);(i)<(k);(i)++) #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; using namespace std; typedef long long int ll; const ll INF = 10241024; const int MOD = 1e9 + 7; int N,C,V; struct edge { int from, to, cost, longa; }; vector<vector<edge>> dist(51); void input(){ cin >> N >> C >> V; int b[V]; edge a[V]; rep(i, V){ cin >> a[i].from; } rep(i,V){ cin >> a[i].to;a[i].to--; } rep(i,V) cin >> a[i].cost; rep(i,V)cin >> a[i].longa; rep(i,V) { dist[a[i].from].push_back(a[i]); } } void solve(){ input(); int dp[N][C];//i番目に行くときc円で行ったならそのとき掛かった時間の最小値をdp[i][c]とする rep(i,N)rep(j,C) dp[i][j] = INF; dp[0][0] = 0; queue<edge> q; for(int i=0;i<dist[0].size();i++){ q.push(dist[0][i]); } int loc = 0; while(!q.empty()) { edge e = q.front();q.pop(); for(int i=0;i<dist[e.to].size();i++){ q.push(dist[e.to][i]); } for(int i=0;i<C;i++){ if(i+e.cost > C) break; if(dp[e.to][i+e.cost] != INF) { chmin(dp[e.to][i+e.cost], dp[e.from][i] + e.cost) } else { dp[e.to][i+e.cost] = e.cost; } } } int ans = INF; rep(i,C){ chmin(ans ,dp[N][i]); } cout << ans << endl; } int main () { solve(); return 0; }