SHARE
TWEET

COI get Raid

Slayerfeed Apr 21st, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <utility>
  5.  
  6. using namespace std;
  7. using  pii = pair<int,int>;
  8. int main(){
  9.     int n;
  10.     cin >> n;
  11.     int w[n+1];
  12.  
  13.     for(int i=1;i<=n;++i){
  14.         cin >> w[i];
  15.     }
  16.     int m;
  17.     cin >> m;
  18.     int u1,v1;
  19.     vector <int> g[n+1];
  20.     for(int i=0;i<m;++i){
  21.         cin >> u1 >> v1;
  22.        g[u1].push_back(v1);
  23.        g[v1].push_back(u1);
  24.     }
  25.  
  26.     vector<int> dist(n+1,2e9);
  27.     vector<bool> visited(n+1,false);
  28.     priority_queue<pii, vector<pii>, greater<pii>> q;
  29.  
  30.     dist[1]=0;
  31.     q.push({dist[1],1});
  32.     int sum = 0;
  33.     while(!q.empty()){
  34.         int u=q.top().second , d=q.top().first;
  35.         q.pop();
  36.  
  37.         if(visited[u]){
  38.             continue;
  39.         }
  40.         visited[u]=true;
  41.         sum+=dist[u];
  42.  
  43.         for(auto c:g[u]){
  44.                int z=w[u]+w[c];
  45.             if(!visited[c]&&z<dist[c]){
  46.                 dist[c]=z;
  47.                 q.push({dist[c],c});
  48.             }
  49.         }
  50.     }
  51.  
  52.     cout << sum;
  53.  
  54.     return 0;
  55. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top