//Solution to Viral Hotel problem by writer: BortiK #include using namespace std; int main(){ int N, K, M, P; cin >> N >> K >> M >> P; vector> adj(N); for(int i = 0; i < M; i++){ int u,v; cin >> u >> v; u--;v--; adj[u].push_back(v); adj[v].push_back(u); } vector s(N); for(int i = 0; i < N; i++){ cin >> s[i]; } priority_queue, vector>, greater>> todo; vector infected(N, -1); for(int i = 0; i < K; i++){ int x; cin >> x; x--; todo.push(make_pair(s[x],x)); infected[x] = 0; } vector quar(N, -1); int answer = 0; while(!todo.empty()){ pair x = todo.top(); todo.pop(); if(quar[x.second] != -1 && quar[x.second] < x.first) continue; for(int u: adj[x.second]){ if(infected[u] == -1){ infected[u] = x.first; todo.push(make_pair(x.first+s[u], u)); } else { if(infected[u]+P > x.first){ if(quar[u] == -1){ answer++; quar[u] = x.first; } } } } } cout << answer; }