結果

問題 No.1 道のショートカット
コンテスト
ユーザー Roki
提出日時 2017-03-14 15:49:05
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0