結果

問題 No.1 道のショートカット
ユーザー mukadenodaiou
提出日時 2018-03-29 13:46:32
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,676 bytes
コンパイル時間 859 ms
コンパイル使用メモリ 97,364 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 16:35:42
合計ジャッジ時間 2,022 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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