結果

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

ソースコード

diff # 

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