#include // graph/graph-template.hpp // graph/graph.hpp #include #include // graph/edge.hpp namespace nono { // brief: // - Edge構造体 // // tparam: // - `T`: 重みの型 // // note: // - `from`, `to`, `weight` がないと、他のライブラリが壊れる template struct Edge { using value_type = T; int from; int to; T weight; int index; // brief: // - Edgeコンストラクタ Edge(int from, int to, const T& weight = 1, int index = -1) : from(from), to(to), weight(weight), index(index) {} friend auto operator<=>(const Edge& lhs, const Edge& rhs) { return lhs.weight <=> rhs.weight; } }; } // namespace nono namespace nono { // brief: // - グラフ構造体 // // tparam: // - `T`: 辺の重みの型 // - `directed`: 有向かどうか // // note: // - 有向グラフのaliasとして `DiGraph` が存在する // - 以下の条件が満たさないと壊れる // \ \ 1. `size()` が頂点数を返す // \ \ 2. `operator[]` が `range-based for` に対応している template class Graph { using EdgeType = Edge; using EdgesType = std::vector; public: using value_type = EdgesType; Graph() = default; explicit Graph(int vertex_size) : vertex_size_(vertex_size), edge_size_(0), adj_list_(vertex_size) {} Graph(int vertex_size, const std::vector& edges) : vertex_size_(vertex_size), edge_size_(0), adj_list_(vertex_size) { for (const auto& e: edges) { adj_list_[e.from].emplace_back(e); } } // brief: // - 頂点数を取得する int size() const { return vertex_size_; } // brief: // - 頂点 `i` に隣接する頂点を取得する const std::vector& operator[](int i) const { return adj_list_[i]; } // brief: // - 頂点 `i` に隣接する頂点を取得する std::vector& operator[](int i) { return adj_list_[i]; } // brief: // - グラフに辺を追加する // // note: // - weightのデフォルト値は1 void add_edge(int from, int to, T weight = static_cast(1), int index = -1) { adj_list_[from].emplace_back(from, to, weight, index); if (not directed) adj_list_[to].emplace_back(to, from, weight, index); edge_size_++; } // brief: // - 頂点 `i` の次数を取得する // // note: // - 有向グラフの場合、出次数を取得する int degree(int i) const { return adj_list_[i].size(); } // brief: // - 頂点の次数の配列を取得する // // note: // - 有向グラフの場合、出次数を取得する std::vector degree() const { std::vector result(vertex_size_); for (int i = 0; i < vertex_size_; i++) { result[i] = adj_list_[i].size(); } return result; } // brief: // - 辺の配列に取得する // // note: // - 単純グラフでないと壊れる std::vector to_edges() const { std::vector edges(edge_size_); int count = 0; for (int u = 0; u < vertex_size_; u++) { for (const auto& e: adj_list_[u]) { if (directed || e.from <= e.to) { edges[count] = e; count++; } } } return edges; } private: int vertex_size_; int edge_size_; std::vector> adj_list_; }; // brief: // - 有向グラフ構造体 // // tparam: // - `T`: 辺の重みの型 // // note: // - `Graph` のalias template using DiGraph = Graph; } // namespace nono namespace nono { // type 1: 回復 // type 2: 感染 struct Event { int time; int type; int index; Event(int time, int type, int index): time(time), type(type), index(index) {} }; bool operator<(const Event& lhs, const Event& rhs) { if (lhs.time == rhs.time and lhs.type == rhs.type) return lhs.index > rhs.index; if (lhs.time == rhs.time) return lhs.type > rhs.type; return lhs.time > rhs.time; } void solve() { int N, M, K, P; std::cin >> N >> K >> M >> P; Graph graph(N); for (int i = 0; i < M; i++) { int u, v; std::cin >> u >> v; u--; v--; graph.add_edge(u, v); } std::vector s(N); for (int i = 0; i < N; i++) std::cin >> s[i]; std::priority_queue events; std::vector kansen(N); std::vector keneki(N); std::vector meneki(N); for (int i = 0; i < K; i++) { int x; std::cin >> x; x--; kansen[x] = true; events.emplace(P, 1, x); events.emplace(s[x], 2, x); } std::set used; while (not events.empty()) { auto event = events.top(); events.pop(); if (used.contains(event)) continue; used.insert(event); auto [time, type, u] = event; if (keneki[u]) continue; if (type == 1) { meneki[u] = true; } else { for (const auto& e: graph[u]) { if (meneki[e.to]) continue; if (keneki[e.to]) continue; if (not kansen[e.to]) { events.emplace(time + P, 1, e.to); events.emplace(time + s[e.to], 2, e.to); kansen[e.to] = true; } else { keneki[e.to] = true; } } } } std::cout << std::accumulate(keneki.begin(), keneki.end(), 0LL) << std::endl; } } // namespace nono int main() { std::cin.tie(0)->sync_with_stdio(0); std::cout << std::fixed << std::setprecision(15); int t = 1; // std::cin >> t; while (t--) nono::solve(); }