#1193823 (C++23(gcc16)) No.2431 Viral Hotel

• 問題: No.2431 Viral Hotel
• ユーザー: hikoten
• 提出日時: 2026-10-20 11:59:12
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 62 ms / 2,000 ms
• コード長: 3,520 bytes
• コンパイル時間: 5,590 ms
• コンパイル使用メモリ: 394,752 KB
• 実行使用メモリ: 15,112 KB
• 最終ジャッジ日時: 2026-10-23 13:55:19
• 合計ジャッジ時間: 9,083 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge2_0

ファイルパターン	結果
sample	AC * 4
other	AC * 43

ソースコード

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG //[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意
#endif


#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using llll = __int128_t;
using namespace atcoder;
using Pll = pair<ll,ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using Graph = vector<vector<ll>>;
#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++)//i=s,s+1...n-1 ノーマルfor 半開区間 
#define dfor(i,s,n) for(ll i = (s)-1; i>=n;i--)//s-1スタートでnまで落ちる
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
template<class T> bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template<class T> 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<<endl
//mint::set_mod(m);//main関数下で扱う用
const ll dx[8] = {1,0,-1,0,1,1,-1,-1};
const ll dy[8] = {0,1,0,-1,1,-1,-1,1};
 
 
 
 
 
 
 
 
void solve(){
 
 
 //ことが起こる日だけシミュレーションするか。
 ll n,k,m,P;
 cin >> n >> k >> m >> P;
 //状態配列を用意するか
 vll condi(n+9);//0 健康、1、感染、2検疫,3回復
Graph G(n+9);

priority_queue<Pll,vector<Pll>,greater<Pll>> regi;
priority_queue<Pll,vector<Pll>,greater<Pll>> 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<ll> 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;
}