結果
問題 | No.1 道のショートカット |
ユーザー |
|
提出日時 | 2014-10-02 02:58:16 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,327 bytes |
コンパイル時間 | 981 ms |
コンパイル使用メモリ | 71,236 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:05:33 |
合計ジャッジ時間 | 2,478 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <cstdio> #include <iostream> #include <vector> #include <set> using namespace std; #define ITER(c) __typeof__((c).begin()) #define FOREACH(it, c) for (ITER(c) it=(c).begin(); it != (c).end(); ++it) #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) #define pb push_back #define mp make_pair int N,C,V; int S[1501],T[1501],Y[1501],M[1501]; 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]; vector<pair<int,pair<int,int> > > v[51]; set< pair<int,int> > vq[51]; REP(i,V) v[S[i]-1].pb(mp(T[i]-1,mp(Y[i],M[i]))); vq[0].insert(mp(0,0)); REP(i,N){ int minm = 1<<29; FOREACH(it, vq[i]){ int y = it->first, m = it->second; if(minm <= m) continue; minm = m; //fprintf(stderr, "i = %d, y = %d, m = %d\n", i, y, m); FOREACH(jt, v[i]){ int t = jt->first, ny = y + jt->second.first, nm = m + jt->second.second; if(ny <= C){ vq[t].insert(mp(ny,nm)); } } } } int minv = 1<<29; FOREACH(it, vq[N-1]){ minv = min(minv, it->second); } if(minv == 1<<29) minv = -1; cout << minv << endl; return 0; }