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

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	satori16
提出日時	2016-08-06 08:14:27
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 5,000 ms
コード長	3,379 bytes
コンパイル時間	991 ms
コンパイル使用メモリ	100,816 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-20 16:24:40
合計ジャッジ時間	2,013 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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	3 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	3 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	1 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	1 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	3 ms 5,376 KB
testcase_24	AC	3 ms 5,376 KB
testcase_25	AC	1 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	3 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	3 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <tuple>
#include <cstdint>
#include <map>
#include <limits>

//copyright Yakitori@2016.

typedef std::vector<std::uint64_t> Vec;
typedef std::tuple<std::uint64_t, std::uint64_t, std::uint64_t, Vec, Vec, Vec, Vec> DType;
typedef std::tuple<std::uint64_t, std::uint64_t, std::uint64_t> ND;//to,money cost,time cost.
typedef std::map<std::uint64_t, std::vector<ND>> NType;//from.node.
typedef std::tuple<std::uint64_t, std::uint64_t, NType> PType;//count,money,node.

DType MakeTest1() {
	std::uint64_t N = 3;//count the town.
	std::uint64_t C = 100;//having money.
	std::uint64_t V = 3;//max road
	Vec S{ 1,2,1 };//from
	Vec T{ 2,3,3 };//to
	Vec Y{ 10,90,10 };//cost of money
	Vec M{ 10,10,50 };//cost of time

	return std::make_tuple(N, C, V, S, T, Y, M);
}
DType MakeTest2() {
	std::uint64_t N = 3;//count the town.
	std::uint64_t C = 100;//having money.
	std::uint64_t V = 3;//max road
	Vec S{ 1,2,1 };//from
	Vec T{ 2,3,3 };//to
	Vec Y{ 1,100, 10 };//cost of money
	Vec M{ 10,10,50 };//cost of time

	return std::make_tuple(N, C, V, S, T, Y, M);
}
DType MakeTest3() {
	std::uint64_t N = 10;//count the town.
	std::uint64_t C = 10;//having money.
	std::uint64_t V = 19;//max road
	Vec S{1,1,2 ,4,5 ,1,3,4,6,4,6,4,5,7,8,2 ,3 ,4 ,9  };//from
	Vec T{3,5,5 ,5,6 ,7,7,7,7,8,8,9,9,9,9,10,10,10,10  };//to
	Vec Y{8,6,8 ,7,6 ,6,9,9,7,6,9,7,7,8,7,6 ,6 ,8 ,6  };//cost of money
	Vec M{8,9,10,4,10,3,5,9,3,4,1,8,3,1,3,6 ,6 ,10,4  };//cost of time

	return std::make_tuple(N, C, V, S, T, Y, M);
}
DType GetInput() {
	std::uint64_t N = 0;//count the town.
	std::uint64_t C = 0;//having money.
	std::uint64_t V = 0;//max road
	Vec S;//from
	Vec T;//to
	Vec Y;//cost of money
	Vec M;//cost of time
	std::uint64_t Val = 0;

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

	for (std::uint64_t i = 0; i < V; i++) {
		std::cin >> Val;
		S.push_back(Val);
	}
	for (std::uint64_t i = 0; i < V; i++) {
		std::cin >> Val;
		T.push_back(Val);
	}
	for (std::uint64_t i = 0; i < V; i++) {
		std::cin >> Val;
		Y.push_back(Val);
	}
	for (std::uint64_t i = 0; i < V; i++) {
		std::cin >> Val;
		M.push_back(Val);
	}
	return std::make_tuple(N, C, V, S, T, Y, M);
}

PType Convert(DType& D) {
	NType N;
	for (std::size_t i = 0; i < std::get<2>(D); i++) {
		N[std::get<3>(D)[i]].push_back(std::make_tuple(std::get<4>(D)[i], std::get<5>(D)[i], std::get<6>(D)[i]));
	}

	return std::make_tuple(std::get<0>(D), std::get<1>(D), N);
}

bool Rec(const std::uint64_t& N,std::uint64_t Cost,std::uint64_t Time,std::uint64_t& TMax,Vec& V,Vec& VR,PType& P) {
	
	if (Time > TMax) {
		return false;
	}
	if (Cost > std::get<1>(P)) {
		return false;
	}
	if (N == std::get<0>(P)) {
		VR = V;
		TMax = Time;
		return true;
	}

	std::vector<ND> &F = std::get<2>(P)[N];

	for (auto& o : F) {
		V.push_back(std::get<0>(o));
		Rec(V.back(), Cost + std::get<1>(o), Time + std::get<2>(o), TMax, V, VR, P);
		V.pop_back();
	}

	return false;
}

std::int64_t MakeHoge(PType& P) {
	Vec Road;
	Vec Best;
	std::uint64_t TM = std::numeric_limits < std::uint64_t>::max() / 2;
	Rec(1, 0, 0, TM , Road, Best, P);

	return (Best.size()==0) ? -1:TM;
}

int main() {
	//DType D = MakeTest1();//20
	//DType D = MakeTest2();//50
	//DType D = MakeTest3();//-1
	DType D = GetInput();//from STDIN.
	PType P = Convert(D);
	std::int64_t R;

	R = MakeHoge(P);

	std::cout << R << std::endl;

	return 0;
}

yukicoder

結果

テストケース

ソースコード