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

• 問題: No.1 道のショートカット
• ユーザー: やまぞう
• 提出日時: 2015-03-05 01:29:26
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 3 ms / 5,000 ms
• コード長: 2,982 bytes
• コンパイル時間: 772 ms
• コンパイル使用メモリ: 77,564 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-20 16:10:54
• 合計ジャッジ時間: 2,024 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 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	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	3 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	3 ms; 5,376 KB
testcase_12	AC	3 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	2 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	1 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	2 ms; 5,376 KB
testcase_26	AC	2 ms; 5,376 KB
testcase_27	AC	3 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	3 ms; 5,376 KB
testcase_32	AC	2 ms; 5,376 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	3 ms; 5,376 KB
testcase_35	AC	2 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	2 ms; 5,376 KB
testcase_42	AC	1 ms; 5,376 KB
testcase_43	AC	2 ms; 5,376 KB

ソースコード

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

class Route
{
public:
	int town1;
	int town2;
	int cost;
	int time;

	Route()
	{
	}

	Route(const Route& src)
		: town1(src.town1), town2(src.town2), cost(src.cost), time(src.time)
	{
	}

	Route(int town1, int town2, int cost, int time)
		: town1(town1), town2(town2), cost(cost), time(time)
	{
	}

	Route& operator=(const Route& src)
	{
		if (&src != this) {
			town1 = src.town1;
			town2 = src.town2;
			cost = src.cost;
			time = src.time;
		}
		return *this;
	}
};

int N;
int C;
int V;
vector<Route> routes;

bool input(istream& in)
{
	if (!(in >> N)) return false;
	in >> C;
	in >> V;
	routes.resize(V);
	for (int i = 0; i < V; i++) in >> routes[i].town1;
	for (int i = 0; i < V; i++) in >> routes[i].town2;
	for (int i = 0; i < V; i++) in >> routes[i].cost;
	for (int i = 0; i < V; i++) in >> routes[i].time;
	return true;
}

class RouteState
{
public:
	int cost;
	int time;
	RouteState()
		: cost(0), time(0)
	{
	}

	RouteState(const RouteState& src)
		: cost(src.cost), time(src.time)
	{
	}

	RouteState(int cost, int time)
		: cost(cost), time(time)
	{
	}

	RouteState& operator=(const RouteState& src)
	{
		if (&src != this) {
			cost = src.cost;
			time = src.time;
		}
		return *this;
	}
};

struct less_RouteState
{
	bool operator()(const RouteState& a, const RouteState& b) {
		return a.time < b.time;
	}
};

int resolve()
{
	vector<vector<int>> route_indexes(N);
	for (int i = 0; i < V; i++) {
		route_indexes[routes[i].town1 - 1].push_back(i);
	}

	vector< vector<RouteState> > town_state(N);
	town_state[0].push_back(RouteState(0, 0));
	for (int src_town = 0; src_town < N; src_town++) {
		for (auto& src_town_state : town_state[src_town]) {
			for (auto& route_index : route_indexes[src_town]) {
				auto& route = routes[route_index];
				int next_cost = src_town_state.cost + route.cost;
				int next_time = src_town_state.time + route.time;
				if (next_cost <= C) {
					auto& dst_town_state = town_state[route.town2 - 1];
					bool can_add = true;
					for (auto& town_to_item : dst_town_state) {
						if (next_cost > town_to_item.cost && next_time > town_to_item.time) {
							can_add = false;
							break;
						}
						if (next_cost < town_to_item.cost && next_time < town_to_item.time) {
							town_to_item.cost = next_cost;
							town_to_item.time = next_time;
							can_add = false;
							break;
						}
					}
					if (can_add) {
						dst_town_state.push_back(RouteState(next_cost, next_time));
					}
				}
			}
		}
	}
	auto& last_town = town_state.back();
	auto ite = min_element(last_town.begin(), last_town.end(), less_RouteState());
	if (ite != town_state.back().end()) {
		return ite->time;
	}
	return -1;
}

int main(int argc, char **argv)
{
	if (argc > 1) {
		ifstream stream(argv[1]);
		while (input(stream)) {
			cout << resolve() << endl;
		}
	}
	else {
		while (input(cin)) {
			cout << resolve() << endl;
		}
	}

}