結果
| 問題 | No.2805 Go to School |
| ユーザー |
 nouka28
|
| 提出日時 | 2024-07-12 21:35:41 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 227 ms / 2,000 ms |
| コード長 | 13,091 bytes |
| コンパイル時間 | 5,979 ms |
| コンパイル使用メモリ | 330,340 KB |
| 実行使用メモリ | 22,156 KB |
| 最終ジャッジ日時 | 2024-07-16 01:38:17 |
| 合計ジャッジ時間 | 10,009 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 35 |
ソースコード
#pragma region template/*template made by nouka28last update 2024.7.7*///include#include<bits/stdc++.h>using namespace std;//atcoder#include<atcoder/all>using namespace atcoder;using mint=atcoder::modint998244353;// using mint=atcoder::modint1000000007;// using mint=atcoder::modint;istream& operator>>(istream&is,mint &x){long long x_;is>>x_;x=x_;return is;}ostream& operator<<(ostream&os,mint &x){os<<x.val();return os;}//pragma#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")//define// #define int long long#define pb push_back#define eb emplace_back#define ep emplace#define fi first#define se second#define ALL(x) begin(x),end(x)#define LEN(x) (signed int)(x.size())#define BIT(x,i) ((x)>>(i)&1)//usingusing u32=unsigned int;using u64=unsigned long long;using ull=unsigned long long;using i32=signed int;using i64=signed long long;using ll=signed long long;using f64=double;using f80=long double;using pi=pair<i32,i32>;using pl=pair<i64,i64>;using pd=pair<f80,f80>;template<class T>using V=vector<T>;template<class T>using VV=V<V<T>>;template<class T>using VVV=V<V<V<T>>>;template<class T>using VVVV=V<V<V<V<T>>>>;template<class T>using VVVVV=V<V<V<V<V<T>>>>>;template<class T>using pqmax=priority_queue<T>;template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;using u128=__uint128_t;using i128=__int128_t;//io INT128i128 i128_parse(string &s){i128 ret=0;for(i32 i=0;i<(i32)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+s[i]-'0';return ret;}u128 u128_parse(string &s){u128 ret=0;for(i32 i=0;i<(i32)s.length();i++)if('0'<=s[i]&&s[i]<='9')ret=10*ret+s[i]-'0';return ret;}istream &operator>>(istream &is,i128 &x){string s;is>>s;x=i128_parse(s);return is;}istream &operator>>(istream &is,u128 &x){string s;is>>s;x=u128_parse(s);return is;}ostream &operator<<(ostream &os,i128 x){ostream::sentry s(os);if(s){u128 tmp=x<0?-x:x;char buffer[128];char *d=end(buffer);do{--d;*d="0123456789"[tmp%10];tmp/=10;}while(tmp!=0);if(x<0){--d;*d='-';}int len=end(buffer)-d;if (os.rdbuf()->sputn(d,len)!=len){os.setstate(ios_base::badbit);}}return os;}//constconst i64 LINF=0x1fffffffffffffff;const i32 INF=0x3fffffff;const i64 MOD=998244353;const i64 MOD2=1000000007;const f80 PI=3.1415926535897932384626433832795028841971;const f80 DINF=numeric_limits<f80>::infinity();const f80 EPS=1e-9;const i64 di[]={0,1,0,-1,1,-1,1,-1};const i64 dj[]={1,0,-1,0,1,1,-1,-1};//function#define overload4(_1,_2,_3,_4,name,...) name#define overload3(_1,_2,_3,name,...) name#define rep1(n) for(i64 i=0;i<n;i++)#define rep2(i,n) for(i64 i=0;i<n;i++)#define rep3(i,a,b) for(i64 i=a;i<b;i++)#define rep4(i,a,b,c) for(i64 i=a;i<b;i+=c)#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)#define rrep1(n) for(i64 i=n;i--;)#define rrep2(i,n) for(i64 i=n;i--;)#define rrep3(i,a,b) for(i64 i=b;i-->(a);)#define rrep4(i,a,b,c) for(i64 i=(a)+((b)-(a)-1)/(c)*(c)i>=a;i-=c)#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)#define SUM(...) accumulate(ALL(__VA_ARGS__),i64(0))#define DSUM(...) accumulate(ALL(__VA_ARGS__),f80(0))template<class T>bool chmin(T &x,const T&y){if(x>y){x=y;return true;}return false;}template<class T>bool chmax(T &x,const T&y){if(x<y){x=y;return true;}return false;}template<class T>i32 lob(const V<T>&arr,const T&v){return (i32)(lower_bound(ALL(arr),v)-arr.begin());}template<class T>i32 upb(const V<T>&arr,const T&v){return (i32)(upper_bound(ALL(arr),v)-arr.begin());}template<class T>constexpr auto min(T a,T b,T c){return min(a,min(b,c));}template<class... T>constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}template<class T>constexpr auto max(T a,T b,T c){return max(a,max(b,c));}template<class... T>constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}//iostruct SetUpIO{SetUpIO(){ios::sync_with_stdio(false);cin.tie(nullptr);cout<<fixed<<setprecision(15);}}set_up_io;//invoid scan(char &x){cin>>x;}void scan(u32&x){cin>>x;}void scan(u64 &x){cin>>x;}void scan(i32 &x){cin>>x;}void scan(i64 &x){cin>>x;}void scan(string &x){cin>>x;}void scan(mint &x){cin>>x;}template<class T1,class T2>void scan(pair<T1,T2> &x){scan(x.first);scan(x.second);}template<class T>void scan(V<T> &x){for(T &ele:x){scan(ele);}}template<class T>void scan(deque<T> &x){for(T &ele:x){scan(ele);}}template<class T,i32 size>void scan(array<T,size> &x){for(T &ele:x){scan(ele);}}template<class T,i32 size>void scan(T (&x)[size]){for(T &ele:x){scan(ele);}}void rd(){}template<class Head,class... Tail>void rd(Head &head,Tail &...tail){scan(head);rd(tail...);}#define CHR(...) char __VA_ARGS__;rd(__VA_ARGS__)#define U32(...) u32 __VA_ARGS__;rd(__VA_ARGS__)#define U64(...) u64 __VA_ARGS__;rd(__VA_ARGS__)#define I32(...) i32 __VA_ARGS__;rd(__VA_ARGS__)#define I64(...) i64 __VA_ARGS__;rd(__VA_ARGS__)#define UINT(...) u32 __VA_ARGS__;rd(__VA_ARGS__)#define ULL(...) u64 __VA_ARGS__;rd(__VA_ARGS__)#define INT(...) i32 __VA_ARGS__;rd(__VA_ARGS__)#define LL(...) i64 __VA_ARGS__;rd(__VA_ARGS__)#define STR(...) string __VA_ARGS__;rd(__VA_ARGS__)#define VEC(type,name,size) V<type> name(size);rd(name);#define VVEC(type,name,size1,size2) VV<type> name(size1,V<type>(size2));rd(name)//outvoid print(){putchar(' ');}void print(bool x){printf("%d",x);}void print(u32 x){printf("%u",x);}void print(u64 x){printf("%llu",x);}void print(i32 x){printf("%d",x);}void print(i64 x){printf("%lld",x);}void print(char x){printf("%c",x);}void print(f64 x){printf("%.15f",x);}void print(f80 x){printf("%.15Lf",x);}void print(const string &x){for(auto&&i:x)print(i);}void print(mint x){printf("%d",x.val());}template<class T>void print(const V<T>&);template<class T1,class T2>void print(const pair<T1,T2>&x){print(x.first);putchar(' ');print(x.second);}template<class T>void print(complex<T>&x){if(x.real()>=0)print('+');print(x.real());if(x.imag()>=0)print('+');print(x.imag());print('i');}template<class T>void print(const V<T>&x){if(x.empty())return;print(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}template<class T>void print(const deque<T>&x){if(x.empty())return;print(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}template<class T>void print(const set<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}template<class T>void print(const unordered_set<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}template<class T>void print(const multiset<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}template<class T>void print(const unordered_multiset<T>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}template<class T1,class T2>void print(map<T1,T2>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}template<class T1,class T2>void print(unordered_map<T1,T2>&x){if(x.empty())return;print(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(' ');print(*i);}}template<class T, size_t size> void print(const array<T, size>& x){ print(x[0]); for(auto i = x.begin(); ++i != x.end(); ){ putchar(' '); print(*i);} }template<class T,i32 size>void print(const T(&x)[size]){print(x[0]);for(auto i=x;++i!=end(x);){/*putchar(' ');*/print(*i);}}template<class T>void print(const T&a){cout<<a;}int out(){putchar('\n');return 0;}template<class T>int out(const T&t){print(t);putchar('\n');return 0;}template<class Head,class... Tail>int out(const Head&head,const Tail&...tail){print(head);putchar(' ');out(tail...);return 0;}#ifdef LOCALvoid dbg(){putchar(' ');}void dbg(bool x){printf("%d",x);}void dbg(u32 x){printf("%u",x);}void dbg(u64 x){printf("%llu",x);}void dbg(i32 x){printf("%d",x);}void dbg(i64 x){printf("%lld",x);}void dbg(char x){printf("%c",x);}void dbg(f64 x){printf("%.15f",x);}void dbg(f80 x){printf("%.15Lf",x);}void dbg(const string &x){for(auto&&i:x)dbg(i);}void dbg(mint x){printf("%d",x.val());}template<class T>void dbg(const V<T>&);template<class T1,class T2>void dbg(const pair<T1,T2>&x){putchar('(');dbg(x.first);putchar(',');dbg(x.second);putchar(')');}template<class T>void dbg(complex<T>&x){if(x.real()>=0)dbg('+');dbg(x.real());if(x.imag()>=0)dbg('+');dbg(x.imag());dbg('i');}template<class T>void dbg(const V<T>&x){putchar('[');if(!x.empty()){dbg(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar(']');}template<class T>void dbg(const deque<T>&x){putchar('[');if(!x.empty()){dbg(x[0]);for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar(']');}template<class T>void dbg(const set<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}template<class T>void dbg(const unordered_set<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}template<class T>void dbg(const multiset<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}template<class T>void dbg(const unordered_multiset<T>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}template<class T1,class T2>void dbg(map<T1,T2>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}template<class T1,class T2>void dbg(unordered_map<T1,T2>&x){putchar('{');if(!x.empty()){dbg(*x.begin());for(auto i=x.begin();++i!=x.end();){putchar(',');dbg(*i);}}putchar('}');}template<class T, size_t size> void dbg(const array<T, size>& x){ putchar('[');dbg(x[0]); for(auto i = x.begin(); ++i != x.end(); ){ putchar(',');dbg(*i); } putchar(']');}template<class T,i32 size>void dbg(const T(&x)[size]){/*putchar('[');*/dbg(x[0]);for(auto i=x;++i!=end(x);){/*putchar(' ')*/;dbg(*i);}/*putchar(']');*/}template<class T>void dbg(const T&a){cout<<a;}int dbg2(){putchar('\n');return 0;}template<class T>int dbg2(const T&t){dbg(t);putchar('\n');return 0;}template<class Head,class... Tail>int dbg2(const Head&head,const Tail&...tail){dbg(head);putchar(' ');dbg2(tail...);return 0;}#define debug(...) {dbg((string)(#__VA_ARGS__));dbg(":");dbg2(__VA_ARGS__);}#else#define debug(...) void(0)#endif//randomrandom_device rnd;mt19937 mt(rnd());const i64 MT_MAX=LINF;uniform_int_distribution<i64> RAND(0,MT_MAX);f64 randd(){return 1.0*RAND(mt)/MT_MAX;}//random value [a,b]i64 randint(i64 a,i64 b){return a+RAND(mt)%(b-a+1);}//funtion2#define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__}))vector<vector<i64>> __MAKE_MAT__(vector<i64> v){if(v.empty())return vector<vector<i64>>(1,vector<i64>());i64 n=v.back();v.pop_back();vector<vector<i64>> ret,tmp=__MAKE_MAT__(v);for(auto e:tmp)for(i64 i=0;i<n;++i){ret.push_back(e);ret.back().push_back(i);}return ret;}//V',Pを返す。PはVを昇順に並べた時のidxtemplate<class T>pair<vector<T>,vector<i32>> sortperm(vector<T> v){vector<pair<T,int>> sv;for(i32 i=0;i<(i32)v.size();i++){sv.push_back({v[i],i});}sort(sv.begin(),sv.end());vector<T> rv;vector<i32> p;for(auto[x,idx]:sv){rv.push_back(x);p.push_back(idx);}return {rv,p};}i64 pow(i64 a,i64 b){i64 x=1;while(b){if(b&1){x*=a;}a=a*a;b>>=1;}return x;}bool isupper(char x){return('A'<=x&&x<='Z');}bool islower(char x){return('a'<=x&&x<='z');}char upper(char &x){if(isupper(x)){return x;}return x-'a'+'A';}char lower(char &x){if(islower(x)){return x;}return x-'A'+'a';}string upper(string s){for(auto&e:s)e=upper(e);return s;}string lower(string s){for(auto&e:s)e=lower(e);return s;}bool isdigit(char x){return('0'<=x&&x<='9');}bool ingrid(int x,int y,int h,int w){return 0<=x&&x<h&&0<=y&&y<w;}#pragma endregionvector<ll> dijkstra(vector<vector<pair<ll,ll>>> &g,ll start){priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;vector<bool> kakutei(g.size(),false);vector<ll> dis(g.size(),(ll)LINF);q.push(make_pair(0,start));dis[start]=0;while(!q.empty()){pair<ll,ll> p=q.top();q.pop();ll pos=p.second,cost=p.first;if(kakutei[pos])continue;kakutei[pos]=true;for(auto nex:g[pos]){ll npos=nex.first,ncos=nex.second;if(dis[npos]>cost+ncos){dis[npos]=cost+ncos;q.push(make_pair(dis[npos],npos));}}}return dis;}int main(){LL(n,m,l,S,E);VV<pair<ll,ll>> g(n);rep(i,m){INT(a,b,t);a--;b--;g[a].pb({b,t});g[b].pb({a,t});}auto ds=dijkstra(g,0),dg=dijkstra(g,n-1);V<int> t(l);for(auto&&e:t)cin>>e,e--;ll ans=LINF;for(auto&&e:t){if(ds[e]<S){chmin(ans,dg[e]+S+1);}else if(ds[e]<=S+E-1){chmin(ans,dg[e]+ds[e]+1);}}if(ans==LINF)out(-1);else out(ans);}