#157807 (C++14) No.1 道のショートカット

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	Roki
提出日時	2017-03-14 15:49:05
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	16 ms / 5,000 ms
コード長	1,228 bytes
コンパイル時間	571 ms
コンパイル使用メモリ	68,480 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-20 16:29:00
合計ジャッジ時間	1,589 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	11 ms 5,376 KB
testcase_09	AC	7 ms 5,376 KB
testcase_10	AC	5 ms 5,376 KB
testcase_11	AC	6 ms 5,376 KB
testcase_12	AC	16 ms 5,376 KB
testcase_13	AC	16 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	4 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	3 ms 5,376 KB
testcase_20	AC	3 ms 5,376 KB
testcase_21	AC	3 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	6 ms 5,376 KB
testcase_24	AC	6 ms 5,376 KB
testcase_25	AC	3 ms 5,376 KB
testcase_26	AC	3 ms 5,376 KB
testcase_27	AC	8 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	4 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	9 ms 5,376 KB
testcase_33	AC	5 ms 5,376 KB
testcase_34	AC	6 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	3 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	3 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<algorithm>
#include<iostream>
#include<array>
#include<type_traits>

constexpr std::size_t road_max=1500;
constexpr std::size_t infinity=9999999;

template<class T,std::size_t size>
struct Setter{
	explicit Setter()=default;
	struct decrement;

	template<class Tag=std::nullptr_t>
	void set(const std::size_t in)
	{
		std::cin>>ar_[in];
		if(std::is_same<Tag,Setter::decrement>::value)--ar_[in];
	}

	T& operator[](std::size_t in){return ar_[in];}
	std::array<T,size> ar_;
};

int main()
{
	std::size_t N{},C{},V{};
	std::array<std::array<std::size_t,301>,50> ct{};
	for(auto& ar:ct)std::fill(ar.begin(),ar.end(),infinity);

	using Set=Setter<std::size_t,road_max>;
	Set S{},T{},Y{},M{};

	std::cin>>N>>C>>V;

#define REP_V for(std::size_t i=0; i<V; ++i)	
	REP_V S.set<Set::decrement>(i); REP_V T.set<Set::decrement>(i);
	REP_V Y.set<>(i); REP_V M.set<>(i);
	
	ct[0][C]=0;
	for(std::size_t i=0; i<N; ++i)
		for(std::size_t j=0; j<=C; ++j)
			for(std::size_t k=0; k<V; ++k)
				if(S[k]==i and Y[k]<=j)
					ct[T[k]][j-Y[k]]=std::min(ct[T[k]][j-Y[k]],ct[i][j]+M[k]);

	std::size_t rs=infinity;
	for(std::size_t i=0; i<=C; ++i)rs=std::min(rs,ct[N-1][i]);
	std::cout<<static_cast<signed>((rs==infinity?-1:rs))<<std::endl;
}

yukicoder

結果

テストケース

ソースコード