結果

問題 No.1 道のショートカット
ユーザー やまぞうやまぞう
提出日時 2015-03-05 01:59:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 2,515 bytes
コンパイル時間 768 ms
コンパイル使用メモリ 78,560 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 16:11:18
合計ジャッジ時間 1,926 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 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 3 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 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 1 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 2 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 2 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 3 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 2 ms
5,376 KB
testcase_43 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct Route
{
	int town1;
	int town2;
	int cost;
	int time;

	Route() {}

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

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

struct RouteState
{
	int cost;
	int time;

	RouteState() {}

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

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& dst_town_state_item : dst_town_state) {
						if (next_cost > dst_town_state_item.cost && next_time > dst_town_state_item.time) {
							can_add = false;
							break;
						}
					}
					if (can_add) {
						for (size_t i = 0; i < dst_town_state.size(); i++) {
							if (dst_town_state[i].cost > next_cost && dst_town_state[i].time > next_time) {
								dst_town_state.erase(dst_town_state.begin() + i);
								i--;
							}
						}
						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