結果
問題 | No.1 道のショートカット |
ユーザー | hspop1 |
提出日時 | 2017-05-05 18:58:27 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,195 bytes |
コンパイル時間 | 570 ms |
コンパイル使用メモリ | 68,744 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2024-07-08 04:51:56 |
合計ジャッジ時間 | 7,088 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | TLE | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
ソースコード
#include <iostream> #include <iterator> #include <cstdlib> #include <sstream> #include <string> #include <vector> #include <algorithm> #include <iterator> static const int MAX_RESULT = 10000000; struct InputDataInfo { int max_town_no_; int max_money_; std::vector<int> start_city_; std::vector<int> end_city_; std::vector<int> cost_; std::vector<int> time_; int result_; InputDataInfo() : max_town_no_(-1) , max_money_(0) , result_(MAX_RESULT) {} }; void find_next_data(std::vector<int>::iterator* sIter, int running_cost, int running_time, int current_city, InputDataInfo& info) { auto f_check_end = [](int cost, int time, InputDataInfo& info) { if (cost <= info.max_money_) { if (time < info.result_) { info.result_ = time; } } }; while (1) { *sIter = std::find(*sIter, info.start_city_.end(), current_city); if (*sIter == info.start_city_.end()) { break; } int next_city = -1; const bool is_erase = (current_city == 1); size_t index = std::distance(info.start_city_.begin(), *sIter); if (index < info.end_city_.size()) { next_city = info.end_city_[index]; if (is_erase) { *sIter = info.start_city_.erase(info.start_city_.begin() + index); info.end_city_.erase(info.end_city_.begin() + index); } else { ++(*sIter); } } if (index < info.cost_.size()) { if (is_erase) { running_cost = info.cost_[index]; info.cost_.erase(info.cost_.begin() + index); } else { running_cost += info.cost_[index]; } } if (index < info.time_.size()) { if (is_erase) { running_time = info.time_[index]; info.time_.erase(info.time_.begin() + index); } else { running_time += info.time_[index]; } } if (next_city == info.max_town_no_) { f_check_end(running_cost, running_time, info); break; } else { auto tmpo_itr = info.start_city_.begin(); find_next_data(&tmpo_itr, running_cost, running_time, next_city, info); } } } void calc_optimal_root(InputDataInfo& info) { int running_cost = 0; int running_time = 0; int current_city = 1; auto tmpo_itr = info.start_city_.begin(); find_next_data(&tmpo_itr, running_cost, running_time, current_city, info); std::cout << ((info.result_ == MAX_RESULT) ? -1 : info.result_) << std::endl; } int main() { std::string line; int input_count = 0; InputDataInfo info; for (; std::getline(std::cin, line);) { std::istringstream iss(line); switch (input_count) { case 0: // 町の数 iss >> info.max_town_no_; break; case 1: // 手持ち金額 iss >> info.max_money_; break; case 3: // 開始町 std::copy(std::istream_iterator<int>(iss), {}, std::back_inserter(info.start_city_)); break; case 4: // 終点町 std::copy(std::istream_iterator<int>(iss), {}, std::back_inserter(info.end_city_)); break; case 5: // コスト std::copy(std::istream_iterator<int>(iss), {}, std::back_inserter(info.cost_)); break; case 6: // 単位時間 std::copy(std::istream_iterator<int>(iss), {}, std::back_inserter(info.time_)); break; } ++input_count; if (7 <= input_count) { break; } } calc_optimal_root(info); return 0; }