結果
問題 | No.1 道のショートカット |
ユーザー | ignis_fatuus |
提出日時 | 2015-12-17 09:14:07 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 2,046 bytes |
コンパイル時間 | 715 ms |
コンパイル使用メモリ | 75,776 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-27 21:50:31 |
合計ジャッジ時間 | 2,453 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 5 ms
4,376 KB |
testcase_09 | AC | 4 ms
4,380 KB |
testcase_10 | AC | 4 ms
4,376 KB |
testcase_11 | AC | 5 ms
4,376 KB |
testcase_12 | AC | 6 ms
4,380 KB |
testcase_13 | AC | 6 ms
4,376 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | AC | 3 ms
4,376 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 3 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 4 ms
4,376 KB |
testcase_24 | AC | 3 ms
4,376 KB |
testcase_25 | AC | 2 ms
4,376 KB |
testcase_26 | AC | 2 ms
4,376 KB |
testcase_27 | AC | 5 ms
4,380 KB |
testcase_28 | AC | 2 ms
4,376 KB |
testcase_29 | AC | 4 ms
4,376 KB |
testcase_30 | AC | 2 ms
4,376 KB |
testcase_31 | AC | 2 ms
4,376 KB |
testcase_32 | AC | 4 ms
4,380 KB |
testcase_33 | AC | 3 ms
4,380 KB |
testcase_34 | AC | 3 ms
4,380 KB |
testcase_35 | AC | 2 ms
4,380 KB |
testcase_36 | AC | 4 ms
4,376 KB |
testcase_37 | AC | 3 ms
4,380 KB |
testcase_38 | AC | 2 ms
4,376 KB |
testcase_39 | AC | 2 ms
4,380 KB |
testcase_40 | AC | 3 ms
4,380 KB |
testcase_41 | AC | 2 ms
4,376 KB |
testcase_42 | AC | 2 ms
4,376 KB |
testcase_43 | AC | 2 ms
4,376 KB |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<tuple> using namespace std; using Long=long long; using Cost = tuple<Long,Long>; void update_node(vector<Cost>& costs, Cost c) { // cよりも大きいコストがあれば消してcをいれる // cよりも小さいコストがあれば入れない if(any_of(costs.begin(),costs.end(), [&](Cost a) { return (get<0>(a)<=get<0>(c)) && (get<1>(a)<=get<1>(c)); })) { // } else { costs.erase(remove_if(costs.begin(),costs.end(),[&](Cost a){ return (get<0>(a)>=get<0>(c)) && (get<1>(a)>=get<1>(c)); }), costs.end()); costs.push_back(c); } } int main() { int N,C,V; cin >> N >> C >> V; vector<int> S(V),T(V),Y(V), M(V); for(int i=0;i<V;++i) cin >> S[i]; for(int i=0;i<V;++i) cin >> T[i]; for(int i=0;i<V;++i) cin >> Y[i]; for(int i=0;i<V;++i) cin >> M[i]; vector<vector<Cost>> node(N+1); node[1].push_back(Cost{0,0}); for(int i=1;i<=N;++i) { // node iからnode jへのコストを計算 for(int j=1;j<=N;++j) { // iからjへのパスを探す for(int k=0;k<V;++k) { if(S[k]==i && T[k]==j) { for(int l=0;l<node[i].size();++l) { int c1 = get<0>(node[i][l]) + Y[k]; int c2 = get<1>(node[i][l]) + M[k]; Cost c{c1,c2}; // cout << "node " << j+1 << "update (" << i+1 << "->" << j+1 << ")" << endl; update_node(node[j], c); } } } } } //for(int i=0;i<node.size();++i) { // cout << (i+1) << ": "; // disp(node[i]); // cout << endl; //} Long minval = 12e6; for(int i=0;i<node[N].size();++i) { if(get<0>(node[N][i])<=C && get<1>(node[N][i])<minval) { minval = get<1>(node[N][i]); } } cout << (minval==12e6 ? -1 : minval) << endl; }