結果

問題 No.1 道のショートカット
コンテスト
ユーザー data9824
提出日時 2015-06-10 11:57:11
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,176 bytes
コンパイル時間 898 ms
コンパイル使用メモリ 77,916 KB
実行使用メモリ 10,268 KB
最終ジャッジ日時 2024-07-08 04:07:06
合計ジャッジ時間 7,189 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <limits>

using namespace std;

struct Edge {
	Edge(int dest, int cost, int time) : dest(dest), cost(cost), time(time) {}
	int dest;
	int cost;
	int time;
};

int n;
map<int, vector<Edge> > sourceToEdges;

int scan(int city, int cost, int time) {
	if (city == n) {
		return time;
	}
	int minTime = numeric_limits<int>::max();
	for (vector<Edge>::const_iterator it = sourceToEdges[city].begin();
		it != sourceToEdges[city].end();
		++it) {
		if (it->cost <= cost) {
			minTime = min(minTime, scan(it->dest, cost - it->cost, time + it->time));
		}
	}
	return minTime;
}

int main() {
	int c, v;
	cin >> n >> c >> v;
	vector<int> s(v);
	for (int i = 0; i < v; ++i) {
		cin >> s[i];
	}
	vector<int> t(v);
	for (int i = 0; i < v; ++i) {
		cin >> t[i];
	}
	vector<int> y(v);
	for (int i = 0; i < v; ++i) {
		cin >> y[i];
	}
	vector<int> m(v);
	for (int i = 0; i < v; ++i) {
		cin >> m[i];
	}
	for (int i = 0; i < v; ++i) {
		sourceToEdges[s[i]].push_back(Edge(t[i], y[i], m[i]));
	}
	int result = scan(1, c, 0);
	cout << ((result == numeric_limits<int>::max()) ? -1 : result) << endl;
	return 0;
}
0