/* * Loops over all nodes and adds an edge from that node to destination node with cost of group ticket */ #include #include #include #include using namespace std; #define pii pair #define ll long long struct E{ int node; int weight; bool operator<(const E& a) const { return weight > a.weight; } }; vector single_source_dijkstra(vector> & adj){ int n = adj.size(); vector dist(n, LLONG_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(auto edge: adj[u]){ if(d + edge.weight < dist[edge.node]){ dist[edge.node] = d + edge.weight; q.push({edge.node, d + edge.weight}); } } } } return dist; } ll dijkstra(vector> & adj, vector &D, int s){ int n = adj.size(); vector dist(n, INT_MAX); vector visited(n, 0); priority_queue q; q.push({s, 0}); dist[s] = 0; while(!q.empty()){ int u = q.top().node; int d = q.top().weight; q.pop(); if(u == 0){ return d; } if(!visited[u]){ visited[u] = true; for(auto edge: adj[u]){ if(edge.node != 0 && D[u] != D[edge.node]+ edge.weight) continue; // only use shortest paths if(d + edge.weight < dist[edge.node]){ dist[edge.node] = d + edge.weight; q.push({edge.node, d + edge.weight}); } } } } return INT_MAX; } int main(){ int n, m, p, g; cin >> n >> m >> p >> g; vector v(p); for(int i=0;i > v[i]; v[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}); } ll best_cost = 0; auto dist = single_source_dijkstra(adj); for(auto person: v){ best_cost += dist[person]; } for(int i=1; i