結果

問題 No.1 道のショートカット
コンテスト
ユーザー やまぞう
提出日時 2015-03-05 01:29:26
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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