結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2014-12-22 14:58:47 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,139 bytes |
コンパイル時間 | 995 ms |
コンパイル使用メモリ | 84,056 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 16:07:52 |
合計ジャッジ時間 | 1,766 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <map> #define REP(a, b) for(int a=0; a<(int)b; a++) using namespace std; int main(){ int N, C, V; vector <int> S, T, Y, M; map <int, map<int, vector<pair<int, int> > > > keiro; cin >> N >> C >> V; S.resize(V); T.resize(V); Y.resize(V); M.resize(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) keiro[S[i]][T[i]].push_back(pair<int, int>(Y[i], M[i])); int A[N+1][C+1]; REP(i, N+1){ REP(j, C+1){ A[i][j] = 0; } } for(int i=1; i<N; i++){ for(int j=i+1; j<=N; j++){ if(keiro[i].find(j) != keiro[i].end()){ REP(l, keiro[i][j].size()){ int money = keiro[i][j][l].first, time = keiro[i][j][l].second; for(int k=0; k <= (C-money); k++){ if(A[i][k+money]==0 && i!=1) break; A[j][k] = (A[j][k]==0)? A[i][k+money]+time : min(A[j][k], A[i][k+money]+time); } } } } } int min_time = -1; REP(i, C+1){ if(A[N][i]==0) continue; min_time = (min_time==-1) ? A[N][i] : min(A[N][i], min_time); } cout << min_time << endl; return 0; }