Advertisement
Guest User

Untitled

a guest
Mar 5th, 2015
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #define ll long long int
  5. using namespace std;
  6. struct edge
  7. {
  8.     ll vertex,weight;
  9.     edge()
  10.     {
  11.     }
  12.     edge(ll a,ll b)
  13.     {
  14.         vertex=a;
  15.         weight=b;
  16.     }
  17.     bool operator < (const edge &p)
  18.     const
  19.     {
  20.         return weight > p.weight;
  21.     }
  22. };
  23. vector<edge>G[1000002];
  24. bool vis[1000002],f=false;
  25. ll prim()
  26. {
  27.     priority_queue<edge>q;
  28.     ll i,v;
  29.     ll ans=0;
  30.     ll u=1;
  31.     for(i=0;i<G[u].size();i++)
  32.         q.push(G[u][i]);
  33.     vis[u]=true;
  34.     while(!q.empty())
  35.     {
  36.         u=q.top().vertex;
  37.         if(vis[u]==false)
  38.         {
  39.             vis[u]=true;
  40.             ans+=q.top().weight;
  41.         //cout<<q.top().weight<<" "<<q.top().vertex<<endl;
  42.  
  43.             q.pop();
  44.             for(i=0;i<G[u].size();i++)
  45.             {
  46.                 v=G[u][i].vertex;
  47.                 if(vis[v]==false)
  48.                 {
  49.                     //cout<<G[u][i].weight<<" "<<v<<"push"<<endl;
  50.                     q.push(G[u][i]);
  51.                 }
  52.             }
  53.         }
  54.         else
  55.             q.pop();
  56.     }
  57.     return ans;
  58. }
  59. int main()
  60. {
  61.     ll prev,temp,i,n,m,k,u,v,w;
  62.     while(cin>>n)
  63.     {
  64.         if(f==true)
  65.             cout<<endl;
  66.         f=true;
  67.         for(i=1,prev=0;i<n;i++)
  68.         {
  69.             cin>>temp>>temp>>temp;
  70.             prev+=temp;
  71.         }
  72.         cin>>k;
  73.         while(k--)
  74.         {
  75.             cin>>u>>v>>w;
  76.             G[u].push_back(edge(v,w));
  77.             G[v].push_back(edge(u,w));
  78.         }
  79.         cin>>m;
  80.         for(i=0;i<m;i++)
  81.         {
  82.             cin>>u>>v>>w;
  83.             G[u].push_back(edge(v,w));
  84.             G[v].push_back(edge(u,w));
  85.         }
  86.         cout<<prev<<endl<<prim()<<endl;
  87.         for(i=1;i<=n;i++)
  88.         {
  89.             vis[i]=false;
  90.             G[i].clear();
  91.         }
  92.     }
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement