#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG //[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意 #endif #include #include using namespace std; using ll = long long; using ull = unsigned long long; using llll = __int128_t; using namespace atcoder; using Pll = pair; using vll = vector; using vvll = vector>; using vvvll = vector>>; using Graph = vector>; #define rep(i,n) for(ll i = 0; i < (n); ++i) #define rrep(i,n) for(ll i = 1; i <= (n); ++i) #define drep(i,n) for(ll i = (n)-1; i >= 0; --i) #define nfor(i,s,n) for(ll i=s;i=n;i--)//s-1スタートでnまで落ちる #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() template bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; } template bool chmax(T& a, T b) { if(a < b) { a = b; return true; } return false; } const ll inf = 1e18; const ll MOD = 998244353; const ll MOD2 = 1e9 + 7; using mint = modint998244353; //using mint = modint1000000007; //using mint = modint; #define YES cout<<"Yes"<<"\n"; #define NO cout<<"No"<<"\n"; #define YN {cout<<"Yes"<<"\n";}else{cout<<"No"<<"\n";}// if(a==b)YN; #define dame cout<<-1<> n >> k >> m >> P; //状態配列を用意するか vll condi(n+9);//0 健康、1、感染、2検疫,3回復 Graph G(n+9); priority_queue,greater> regi; priority_queue,greater> infect; rep(i,m) { ll u,v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } vll s(n+9); nfor(i,1,n+1) cin >> s[i]; rep(i,k) { ll x; cin >> x; regi.push({P,x}); infect.push({s[x],x}); condi[x] = 1; } ll t = 0; queue ken; while(!regi.empty()||!infect.empty()) { if(regi.empty()&&!infect.empty()) { t = infect.top().first; } else if(!regi.empty()&&infect.empty()) { t = regi.top().first; } else { t = min(infect.top().first,regi.top().first); } //回復 while(!regi.empty()&&t==regi.top().first) { auto[t1,p] = regi.top(); regi.pop(); if(condi[p]==1) { condi[p] = 3; } } while(!infect.empty()&&t==infect.top().first) { auto[t2,p] = infect.top(); infect.pop(); if(condi[p]==1||condi[p]==3) { for(auto nex:G[p]) { if(condi[nex]==0) { condi[nex] = 1; regi.push({t+P,nex}); infect.push({t+s[nex],nex}); } else if(condi[nex]==1) { ken.push(nex); } } } } while(!ken.empty()) { condi[ken.front()] = 2; ken.pop(); } } ll ans = 0; nfor(i,1,n+1) { if(condi[i]==2) ans++; } cout << ans << "\n"; } int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); solve(); return 0; }