#include #include #include #include #include #include using namespace std; #define pii pair struct E{ int node; int weight; bool operator<(const E& a) const { return weight > a.weight; } }; int main(){ int n, m, p, g; cin >> n >> m >> p >> g; vector ps(p); for(int i=0;i > ps[i]; ps[i]--; } vector> adj(n, vector()); for(int i=0; i> a >> b >> c; a--; b--; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } // compute for all nodes the distance to node 0, and also remember the next node on the shortest path vector dist(n, INT_MAX); vector visited(n, 0); priority_queue q; q.push({0, 0}); dist[0] = 0; while(!q.empty()){ int u = q.top().node; int d = q.top().weight; q.pop(); if(!visited[u]){ visited[u] = true; for(const auto &edge: adj[u]){ if(d + edge.weight < dist[edge.node]){ dist[edge.node] = d + edge.weight; q.push({edge.node, d + edge.weight}); } } } } auto dist_index = vector>(n); for(int i=0; i& a, const pair &b){ return a.first > b.first; }); int total_cost = 0; vector congestion = vector(n, 0); for(const auto &loc : ps){ congestion[loc]++; total_cost += dist[loc]; } int best_cost = total_cost; for(const auto &node : dist_index){ int u = node.second; for(const auto &edge : adj[u]){ int v = edge.node; if(dist[v] + edge.weight == dist[u]){ congestion[v] += congestion[u]; } } best_cost = min(best_cost, total_cost - congestion[u] * dist[u] + congestion[u] * g); } cout << best_cost << endl; }