結果

問題 No.2805 Go to School
ユーザー syun0713syun0713
提出日時 2024-07-12 21:52:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 440 ms / 2,000 ms
コード長 9,238 bytes
コンパイル時間 5,163 ms
コンパイル使用メモリ 284,244 KB
実行使用メモリ 31,688 KB
最終ジャッジ日時 2024-07-16 01:39:18
合計ジャッジ時間 12,610 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 199 ms
16,768 KB
testcase_05 AC 352 ms
30,472 KB
testcase_06 AC 159 ms
13,444 KB
testcase_07 AC 168 ms
17,644 KB
testcase_08 AC 329 ms
31,688 KB
testcase_09 AC 157 ms
13,640 KB
testcase_10 AC 193 ms
18,124 KB
testcase_11 AC 440 ms
23,892 KB
testcase_12 AC 281 ms
17,676 KB
testcase_13 AC 419 ms
25,504 KB
testcase_14 AC 54 ms
7,040 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 222 ms
18,944 KB
testcase_19 AC 126 ms
10,336 KB
testcase_20 AC 351 ms
23,884 KB
testcase_21 AC 366 ms
21,628 KB
testcase_22 AC 169 ms
12,776 KB
testcase_23 AC 285 ms
17,652 KB
testcase_24 AC 300 ms
21,020 KB
testcase_25 AC 80 ms
9,160 KB
testcase_26 AC 306 ms
24,372 KB
testcase_27 AC 185 ms
18,560 KB
testcase_28 AC 18 ms
7,296 KB
testcase_29 AC 30 ms
8,320 KB
testcase_30 AC 108 ms
14,588 KB
testcase_31 AC 142 ms
11,624 KB
testcase_32 AC 309 ms
24,336 KB
testcase_33 AC 330 ms
22,724 KB
testcase_34 AC 3 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 135 ms
10,932 KB
testcase_37 AC 129 ms
10,752 KB
testcase_38 AC 251 ms
15,616 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:75:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   75 | void ain(set<T>& Y, auto n) {
      |                     ^~~~
main.cpp:82:26: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   82 | void ain(multiset<T>& Y, auto n) {
      |                          ^~~~

ソースコード

diff # 

/*#pragma GCC target("arch=skylake-avx512")
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")*/
#include<bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
istream& operator>>(istream& is, mint& a) {
	long long v;
	is >> v;
	a = v;
	return is;
}
ostream& operator<<(ostream& os, mint& a) {
	return os << a.val();
}
#endif
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;
using ull = unsigned long long;
using vi = vec<int>;
using vs = vec<string>;
using si = set<int>;
using sll = set<ll>;
using vc = vec<char>;
using vvi = vec<vi>;
using vll = vec<ll>;
using vvll = vec<vll>;
using vsi = vec<si>;
using vsll = vec<sll>;
using vd = vec<double>;
using vvd = vec<vd>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using msi = map<string, int>;
using vpii = vec<pii>;
using vpll = vec<pll>;
using spii = set<pii>;
using spll = set<pll>;
using vb = vector<bool>;
using vvb = vector<vb>;
#define rep(i,j,n) for(ll i=j;i<n;i++)
#define rrep(i,j,n) for (ll i = n-1; i >=j; i--)
#define rp(i,n) rep(i,0,n)
#define rrp(i,n) rrep(i,0,n)
#define all(v) v.begin(), v.end()
#define pb push_back
#define ins insert
#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl; 
#define yn(jg) cout<<(jg? "Yes":"No")<<endl;
#define NL {cout<<endl;}
#define n0 {cout<<"-1"<<endl;}
#define lwb lower_bound
#define upb upper_bound
#define sz size()
#define fi first
#define se second
#define nxp next_permutation
ll mod0 = 998244353, lmax = 2e18, inf = 1050000000;
double pi = 3.141592653589793238462643;
vll vh = { 998244353, 998244853, 1000000007, 1000000009, 1012924417 };
template<typename... T>
void in(T&... X) { (cin >> ... >> X); }
template<typename T>
void ain(vec<T>& Y) { rp(K, Y.size()) cin >> Y[K]; }
template<typename T>
void ain(set<T>& Y, auto n) {
	rp(i, n) {
		T YY; cin >> YY;
		Y.insert(YY);
	}
}
template<typename T>
void ain(multiset<T>& Y, auto n) {
	rp(i, n) {
		T YY; cin >> YY;
		Y.insert(YY);
	}
}
template<typename T>
void ain(pair<T, T> &a) { cin >> a.fi >> a.se; }
template<typename T>
void bin(vec<T>& Z) { rp(L, Z.size()) ain(Z[L]); }
template<typename T>
void aout(T& a) { for (auto I : a) cout << I << " "; cout << endl; }
template<typename T>
void aout(pair<T,T> a) { cout << a.fi << " " << a.se << endl; }
template<typename T>
void aout(queue<T> a) {
	while (!a.empty()) { cout << a.front(); a.pop(); }
}
template<typename T>
void aout(stack<T> a) {
	while (!a.empty()) { cout << a.top(); a.pop(); }
}
#define bout(a) {for(auto J:a) aout(J);}
template<typename T>
bool chmin(T& M1, T M2) {
	if (M1 > M2) { M1 = M2; return 1; }
	else return 0;
}
template<typename T>
bool chmax(T& M1, T M2) {
	if (M1 < M2) { M1 = M2; return 1; }
	else return 0;
}
template<typename T>
auto vmax(T& a) {
	return *max_element(all(a));
}
template<typename T>
auto vmin(T& a) {
	return *min_element(all(a));
}
template<typename T>
auto vmaxi(T& a) {
	return max_element(all(a)) - a.begin();
}
template<typename T>
auto vmini(T& a) {
	return min_element(all(a)) - a.begin();
}
vector<pair<char, ll>>  rle(string rr) {
	vector<pair<char, ll>> ret;
	char lc;
	rep(i, 0, rr.size()) {
		if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++;
		else { ret.pb({ rr[i],1 }); }
		lc = rr[i];
	}
	return ret;
}
vector<pair<int, ll>>  rle(vi rr) {
	vector<pair<int, ll>> ret;
	int lc;
	rep(i, 0, rr.size()) {
		if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++;
		else { ret.pb({ rr[i],1 }); }
		lc = rr[i];
	}
	return ret;
}
vector<pair<ll, ll>>  rle(vll rr) {
	vector<pair<ll, ll>> ret;
	ll lc;
	rep(i, 0, rr.size()) {
		if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++;
		else { ret.pb({ rr[i],1 }); }
		lc = rr[i];
	}
	return ret;
}
template<typename T>
auto lwa(vector<T>& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端)
	auto i = lwb(all(a), b);
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}
template<typename T>
auto lwa(set<T>& a, T b) {//aでbより小さい最大の値のイテレータ
	auto i = a.lwb(b);
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}
template<typename T>
auto lwa(multiset<T>& a, T b) {//aでbより小さい最大の値のイテレータ
	auto i = a.lwb(b);
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}
template<typename T>
auto lwc(vector<T>& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端)
	auto i = lwb(all(a), b);
	if (i != a.end() && *i == b) return i;
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}
template<typename T>
auto lwc(set<T>& a, T b) {//aでb以下の最大の値のイテレータ
	auto i = a.lwb(b);
	if (i != a.end() && *i == b) return i;
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}
template<typename T>
auto lwc(multiset<T>& a, T b) {//aでb以下の最大の値のイテレータ
	auto i = a.lwb(b);
	if (i != a.end() && *i == b) return i;
	if (i == a.begin()) return a.end();
	else i--;
	return i;
}

template<typename T>
vec<T> rsw(vec<T>& a) {//累積和
	vec<T> b = a;
	rep(i, 1, b.size()) b[i] += b[i - 1];
	return b;
}
bool kai(string S) {//回文か判定
	bool ans = 1;
	rp(i, S.size()) if (S[i] != S[S.size() - 1 - i]) ans = 0;
	return ans;
}


sll yk(ll n) {//約数全列挙O(sqrt(N)),set<int>
	sll yaku;
	for (ll i = 1; i * i <= n; i++) if (n % i == 0) {
		yaku.insert(i);
		yaku.insert(n / i);
	}
	return yaku;
}
vi ssa(int n) {//n:必要な素数の最大値 素数全列挙
	vector<int> prime;
	vector<int>lpf(n + 1, 0);
	rep(i, 2, n + 1) {
		if (lpf[i] == 0) {
			lpf[i] = i;
			prime.push_back(i);
		}
		for (int k : prime) {
			if (k * i > n || k > lpf[i]) break;//k最小素因数よりk<=i
			lpf[k * i] = k;//kを最小素因数に持つ数k*iを拾う
		}
	}
	return prime;
}
vector<pll> sib(ll x) {//素因数分解
	if (x == 1) return vector<pll>(1, { 1,1 });
	vector<pll> ans;
	for (ll i = 2; i * i <= x; i++) {//rootx回iを回しxで割る
		ll kaisu = 0;
		while (x % i == 0) {
			x /= i; kaisu++;
		}
		if (kaisu > 0) ans.pb({ i,kaisu });
	}
	if (x != 1) ans.pb({ x,1 });
	return ans;
}
template<typename T>
vec<T> zat(vec<T> a) {//座標圧縮
	auto b = a;
	sort(all(b));
	b.erase(unique(all(b)), b.end());
	vec<T> c(a.size());
	rp(i, a.size()) {
		c[i] = lwb(all(b), a[i]) - b.begin();
	}
	return c;
}
template<typename T>
void cp(map < T, ll >& a, T b, ll c) {//countplus
	if (a.find(b) == a.end()) a[b] = c;
	else a[b] += c;
	if (a[b] == 0) a.erase(b);
}
template<typename T>
vec<T> inv(vec<T> a) {//0-indexed 逆関数(1-indexedは全要素--)
	vec<T> ans(a.sz);
	rp(i, a.sz) {
		ans[a[i]] = i;
	}
	return ans;
}
vll hs(string s) {//hash
	vll r = { 0,0,0,0,0 };
	rp(i, 5) {
		rp(j, s.sz) {
			r[i] *= 27;
			r[i] += (s[j] - 'a' + 1);
			r[i] %= vh[i];
		}
	}
	return r;
}
vll hsp(ll n) {//hashpow
	vll r = { 1,1,1,1,1 };
	rp(i, 5) {
		rp(j, n) {
			r[i] *= 27;
			r[i] %= vh[i];
		}
	}
	return r;
}
template<typename T>
bool cross(T a, T b, T c, T d) {//区間(a,b)と区間(c,d)が重なるか判定
	return !(b <= c || d <= a);
}
template<typename T>
bool crosse(T a, T b, T c, T d) {//区間[a,b]と区間[c,d]が重なるか判定
	return !(b < c || d < a);
}
//lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
//S:中身型 op:左右合成 e:初期値
//F:遅延型 mapping:遅延適用後の要素 composition:遅延合成( 関数f(g()) ) id:遅延初期値(何もさせない)
/*
using S = int;
using F = int;
S op(S a,S b) {
	return a+b;
}

S e() {
	return 0;
}
S mapping(F x, S a) {//xをaに作用(x初期値に注意)
	if (x != 0)return x;
	else return a;
}
F composition(F f, F g) {//fの方が後(f初期値に注意)
	if (f != 0)return f;
	else return g;
}
F id() {return 0;}*/
//cout<<setprecision(15)<<fixed<<
//function<返り値の型(引数の型1, 引数の型2, ...)> 関数名 = [&](引数の型1 引数名1, 引数の型2, 引数名2, ...) 
int main() {
	ll n, m, r, l, s, e; in(n, m, l, s, e); r = 0; e += s;//r:開始地点
	vector<vec<pll>> g(n);
	priority_queue<pll, vec<pll>, greater<pll>> q,qq;
	//g入力
	rp(i, m) {
		ll u, v, d;
		in(u, v, d); u--; v--;
		g[u].pb({ d,v });
		if (u == r) q.push({ d,v });
		if (u == n - 1) qq.push({ d,v });
		g[v].pb({ d,u });
		if (v == r) q.push({d,u});
		if (v == n - 1) qq.push({ d,u });
	}
	
		vll dist(n, lmax);
		dist[r] = 0;
		while (!q.empty()) {
			pll nw = q.top(); q.pop();
			if (chmin(dist[nw.se], nw.fi)) {
				for (auto i : g[nw.se]) {
					q.push({ nw.fi + i.fi,i.se });
				}
			}
		}
	
	vll dist1(n, lmax);
	dist1[n-1] = 0;
	while (!qq.empty()) {
		pll nw = qq.top(); qq.pop();
		if (chmin(dist1[nw.se], nw.fi)) {
			for (auto i : g[nw.se]) {
				qq.push({ nw.fi + i.fi,i.se });
			}
		}
	}
	//aout(dist);
//	aout(dist1);
	set<ll> t;
	rp(i, l) {
		ll x; cin >> x; x--; t.insert(x);
	}
	rp(i, n) {
		auto it = t.find(i);
		if (it == t.end()) dist[i] = lmax;
		else {
			if (dist[i] > e) dist[i] = lmax;
			else chmax(dist[i], s);
			 dist[i]++;
		}
	}
	ll ans = lmax;
	rp(i, n) chmin(ans, dist[i] + dist1[i]);
	//aout(dist);
	//aout(dist1);
	if (ans == lmax) cout << -1;
	else cout << ans;
}
0