結果
問題 |
No.1 道のショートカット
|
ユーザー |
![]() |
提出日時 | 2016-10-26 14:31:15 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,293 bytes |
コンパイル時間 | 744 ms |
コンパイル使用メモリ | 77,176 KB |
実行使用メモリ | 90,140 KB |
最終ジャッジ日時 | 2024-07-08 04:33:51 |
合計ジャッジ時間 | 7,441 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 TLE * 1 -- * 32 |
ソースコード
#include <iostream> #include <cmath> #include <vector> #include <queue> #include <set> #include <sstream> // istringstream #include <algorithm> // sort #include <utility> // pair #include <cfloat> // DBL_MAX typedef long long ll; using namespace std; const int maxN = 50; const int maxM = 1000; struct log { int pos; int cost; int time; }; int main(){ ll N,C,V; // [50],[300],[1500] cin >> N >> C >> V; vector<int> ss(V), ts(V), cs(V), ms(V); for(int i=0; i<V; i++){ cin >> ss[i]; } for(int i=0; i<V; i++){ cin >> ts[i]; } for(int i=0; i<V; i++){ cin >> cs[i]; } for(int i=0; i<V; i++){ cin >> ms[i]; } queue<struct log> roots; struct log tmp = {1,0,0}; roots.push(tmp); int minTime = maxN*maxM; while(true){ if(roots.empty()){ break; } struct log crr = roots.front(); for(int i=0; i<V; i++){ if(ss[i]!=crr.pos){ continue; } if(crr.cost + cs[i] <= C){ if(ts[i]==N){ // goal minTime = min(minTime, ms[i]+crr.time); } else { tmp.pos = ts[i]; tmp.cost = cs[i]+crr.cost; tmp.time = ms[i]+crr.time; roots.push(tmp); } } } roots.pop(); } // if(minTime == maxN*maxM){ minTime = -1; } cout << minTime << endl; return 0; }