結果
問題 | No.1 道のショートカット |
ユーザー | hspop1 |
提出日時 | 2017-05-05 05:32:01 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,113 bytes |
コンパイル時間 | 572 ms |
コンパイル使用メモリ | 69,968 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-08 04:51:45 |
合計ジャッジ時間 | 1,793 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 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 | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | WA | - |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 1 ms
5,376 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | AC | 1 ms
5,376 KB |
testcase_43 | AC | 1 ms
5,376 KB |
ソースコード
#include <iostream> #include <iterator> #include <cstdlib> #include <sstream> #include <string> #include <vector> #include <algorithm> static const int MAX_RESULT = 10000000; struct MoveInfo { 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_; MoveInfo() : max_town_no_(-1) , max_money_(0) , result_(MAX_RESULT) {} }; void calc_optimal_root(MoveInfo& info) { int start_city = 1; int running_cost = 0; int running_time = 0; auto f_check_end = [](int cost, int time, MoveInfo& info) { if (cost <= info.max_money_) { //std::cout << "[SET-01]:" << cost << std::endl; if (time < info.result_) { info.result_ = time; } } }; while(1) { const bool is_erase = (start_city == 1); auto sIter = std::find(info.start_city_.begin() ,info.start_city_.end(), start_city); if (sIter == info.start_city_.end()) { if (is_erase) { //std::cout << "[EXIT]:" << start_city << std::endl; break; } // 道が途絶えている場合 else { //std::cout << "[ERROR]:" << start_city << std::endl; start_city = 1; running_cost = 0; running_time = 0; continue; } } size_t index = std::distance(info.start_city_.begin(), sIter); if (index < info.end_city_.size()) { start_city = info.end_city_[index]; //std::cout << "[INDEX]:" << index << " [NEXT]:" << start_city << std::endl; } if (index < info.cost_.size()) { running_cost += info.cost_[index]; } if (index < info.time_.size()) { running_time += info.time_[index]; } if (start_city == info.max_town_no_) { //std::cout << "[COST]:" << running_cost << " [TIME]:" << running_time << std::endl; f_check_end(running_cost, running_time, info); start_city = 1; running_cost = 0; running_time = 0; } if (is_erase) { info.start_city_.erase(info.start_city_.begin() + index); info.end_city_.erase(info.end_city_.begin() + index); info.cost_.erase(info.cost_.begin() + index); info.time_.erase(info.time_.begin() + index); } } std::cout << ((info.result_== MAX_RESULT) ? -1 : info.result_) << std::endl; } int main() { std::string line; int input_count = 0; MoveInfo 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; }