結果

問題 No.1 道のショートカット
ユーザー やまぞうやまぞう
提出日時 2015-03-05 01:29:26
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,982 bytes
コンパイル時間 652 ms
コンパイル使用メモリ 78,292 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-27 21:40:25
合計ジャッジ時間 2,227 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 3 ms
4,380 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 1 ms
4,376 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 2 ms
4,376 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 2 ms
4,380 KB
testcase_33 AC 2 ms
4,376 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,376 KB
testcase_36 AC 2 ms
4,376 KB
testcase_37 AC 2 ms
4,376 KB
testcase_38 AC 1 ms
4,376 KB
testcase_39 AC 2 ms
4,380 KB
testcase_40 AC 1 ms
4,376 KB
testcase_41 AC 1 ms
4,380 KB
testcase_42 AC 2 ms
4,376 KB
testcase_43 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

}
0