Advertisement
Josif_tepe

Untitled

Sep 24th, 2023
713
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 KB | None | 0 0
  1. #include <queue>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <set>
  7. #include <cstring>
  8. //#include <bits/stdc++.h>
  9. using namespace std;
  10. typedef long long ll;
  11. const int maxn = 1e5 + 10;
  12. const ll INF = 3e16 + 10;
  13. int n, m, k;
  14. vector<pair<int, int> > graph[maxn];
  15. int cities[maxn];
  16. bool to_build[maxn];
  17. struct node {
  18.     int idx;
  19.     ll cost;
  20.    
  21.     node () {}
  22.     node(int _idx, ll _cost) {
  23.         idx = _idx;
  24.         cost = _cost;
  25.     }
  26.     bool operator < (const node &tmp) const {
  27.         return cost > tmp.cost;
  28.     }
  29. };
  30. pair<int, ll> find_nearest_city() {
  31.     vector<ll> dist(n, INF);
  32.     vector<bool> visited(n, false);
  33.     dist[0] = 0;
  34.     priority_queue<node> pq;
  35.     pq.push(node(0, 0));
  36.     while(!pq.empty()) {
  37.         node c = pq.top();
  38.         pq.pop();
  39.         if(visited[c.idx]) continue;
  40.         visited[c.idx] = true;
  41.        
  42.         for(int i = 0; i < (int) graph[c.idx].size(); i++) {
  43.             int neighbour = graph[c.idx][i].first;
  44.             ll weight = graph[c.idx][i].second;
  45.            
  46.            
  47.             if(!visited[neighbour] and c.cost + weight < dist[neighbour]) {
  48.                 dist[neighbour] = c.cost + weight;
  49.                 pq.push(node(neighbour, dist[neighbour]));
  50.             }
  51.         }
  52.     }
  53.     ll shortest_distance = INF;
  54.     int nearest_city = -1;
  55.     for(int i = 0; i < k; i++) {
  56.         if(shortest_distance > dist[cities[i]]) {
  57.             shortest_distance = dist[cities[i]];
  58.             nearest_city = cities[i];
  59.         }
  60.     }
  61.     return make_pair(nearest_city, shortest_distance);
  62. }
  63. ll dijkstra(int S) {
  64.     vector<ll> dist(n, INF);
  65.     dist[S] = 0;
  66.     priority_queue<node> pq;
  67.     pq.push(node(S, 0));
  68.     set<int> st;
  69.     ll result = 0;
  70.     while(!pq.empty() and (int) st.size() < k) {
  71.         node c = pq.top();
  72.         pq.pop();
  73.        
  74.         if(c.cost > dist[c.idx]) continue;
  75.        
  76.         if(to_build[c.idx]) {
  77.             result += c.cost;
  78.             c.cost = 0;
  79.             to_build[c.idx] = false;
  80.             st.insert(c.idx);
  81.         }
  82.         dist[c.idx] = c.cost;
  83.         for(int i = 0; i < (int) graph[c.idx].size(); i++) {
  84.             int neighbour = graph[c.idx][i].first;
  85.             ll weight = graph[c.idx][i].second;
  86.             pq.push(node(neighbour, c.cost + weight));
  87.         }
  88.        
  89.     }
  90.     return result;
  91. }
  92. int main() {
  93.     ios_base::sync_with_stdio(false);
  94.     memset(to_build, false, sizeof to_build);
  95.     cin >> n >> m;
  96.     for(int i = 0; i < m; i++) {
  97.         int a, b, c;
  98.         cin >> a >> b >> c;
  99.         graph[a].push_back(make_pair(b, c));
  100.         graph[b].push_back(make_pair(a, c));
  101.     }
  102.     cin >> k;
  103.     for(int i = 0; i < k; i++) {
  104.         cin >> cities[i];
  105.         to_build[cities[i]] = true;
  106.     }
  107.     pair<int, ll> nearest_city = find_nearest_city();
  108.     ll result = dijkstra(nearest_city.first);
  109.    
  110.     cout << nearest_city.second + result << endl;
  111.    
  112.     return 0;
  113. }
  114.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement