結果

問題 No.1 道のショートカット
ユーザー data9824data9824
提出日時 2015-06-10 11:57:11
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,176 bytes
コンパイル時間 1,193 ms
コンパイル使用メモリ 76,700 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-22 12:21:20
合計ジャッジ時間 7,667 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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