結果

問題 No.1 道のショートカット
ユーザー mukadenodaioumukadenodaiou
提出日時 2018-03-29 13:43:12
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,678 bytes
コンパイル時間 693 ms
コンパイル使用メモリ 97,272 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-08 05:00:36
合計ジャッジ時間 1,704 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long int ll;
const int N = 1000000;
const int INF = 1 << 30;
#define rep(i,n) for(int i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
#define pp pair<ll,ll>
#define fi first
#define se second
string YN(bool b) { return(b ? "YES" : "NO"); }
string yn(bool b) { return(b ? "Yes" : "No"); }
struct edge { ll to; ll c; ll t; };
ll V, E, money,mn=INF;
vector<edge> edges[50];
void dfs(ll pos, ll ti,ll mo,bitset<52>bit2){
	//cout << pos << "," << ti << "," << mo << "," << bit2 << endl;
	if (mo >= money)return;
	if (ti >= mn)return;
	if (pos == V - 1) { if (mo <= money)mn = min(mn, ti); return; }
	bitset<52>bit=bit2; bit[pos] = 1;
	rep(i, (ll)edges[pos].size())if (!bit[edges[pos][i].to]) { dfs(edges[pos][i].to,edges[pos][i].t+ti,edges[pos][i].c+mo,bit); }
}
int main(){
	ll from[1500], to[1500], cost[1500], tm[1500];
	cin >> V >> money >> E;
	rep(i, E)cin >> from[i],from[i]--;
	rep(i, E)cin >> to[i],to[i]--;
	rep(i, E)cin >> cost[i];
	rep(i, E)cin >> tm[i];
	rep(i, E) {
		//if(from[i]==0||from[i]==20||from[i]==26||from[i]==27)cout << from[i] << "," << to[i] << "," << cost[i] << "," << tm[i] << endl;
		edges[from[i]].push_back(edge{to[i], cost[i],tm[i]}); 
	}
	bitset<52>abe;
	dfs(0, 0, 0, abe);
	cout << (mn == INF ? -1:mn) << endl;
	return 0;
}
0