#248039 (C++11) No.1 道のショートカット

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	mukadenodaiou
提出日時	2018-03-29 13:46:32
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2 ms / 5,000 ms
コード長	1,676 bytes
コンパイル時間	793 ms
コンパイル使用メモリ	98,568 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-27 22:14:16
合計ジャッジ時間	1,975 ms
ジャッジサーバーID （参考情報）	judge14 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	2 ms 4,380 KB
testcase_15	AC	1 ms 4,376 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	1 ms 4,380 KB
testcase_19	AC	2 ms 4,376 KB
testcase_20	AC	2 ms 4,380 KB
testcase_21	AC	1 ms 4,380 KB
testcase_22	AC	1 ms 4,380 KB
testcase_23	AC	2 ms 4,380 KB
testcase_24	AC	2 ms 4,376 KB
testcase_25	AC	2 ms 4,376 KB
testcase_26	AC	1 ms 4,380 KB
testcase_27	AC	2 ms 4,380 KB
testcase_28	AC	2 ms 4,376 KB
testcase_29	AC	2 ms 4,376 KB
testcase_30	AC	2 ms 4,380 KB
testcase_31	AC	2 ms 4,376 KB
testcase_32	AC	2 ms 4,380 KB
testcase_33	AC	2 ms 4,380 KB
testcase_34	AC	2 ms 4,380 KB
testcase_35	AC	2 ms 4,380 KB
testcase_36	AC	2 ms 4,376 KB
testcase_37	AC	2 ms 4,376 KB
testcase_38	AC	2 ms 4,376 KB
testcase_39	AC	2 ms 4,376 KB
testcase_40	AC	2 ms 4,380 KB
testcase_41	AC	1 ms 4,376 KB
testcase_42	AC	1 ms 4,376 KB
testcase_43	AC	1 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

# 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;
}

yukicoder

結果

テストケース

ソースコード