結果

問題 No.1 道のショートカット
ユーザー mukadenodaiou
提出日時 2018-03-27 12:47:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,618 bytes
コンパイル時間 844 ms
コンパイル使用メモリ 108,320 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-08 05:00:02
合計ジャッジ時間 1,916 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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 << "," << tm << "," << mo << "," << bit2 << endl;
	if (mo > money)return;
	if (ti > mn)return;
	if (pos == V - 1) { if (mo <= money) { mn = min(mn, ti);} else 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) {
		edges[from[i]].push_back(edge{to[i], cost[i],tm[i]});
		edges[to[i]].push_back(edge{from[i], cost[i],tm[i]});
	}
	bitset<52>abe;
	dfs(0, 0, 0, abe);
	cout << (mn == INF ? -1:mn) << endl;
	return 0;
}
0