Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<queue>
- #define ll long long int
- using namespace std;
- struct edge
- {
- ll vertex,weight;
- edge()
- {
- }
- edge(ll a,ll b)
- {
- vertex=a;
- weight=b;
- }
- bool operator < (const edge &p)
- const
- {
- return weight > p.weight;
- }
- };
- vector<edge>G[1000002];
- bool vis[1000002],f=false;
- ll prim()
- {
- priority_queue<edge>q;
- ll i,v;
- ll ans=0;
- ll u=1;
- for(i=0;i<G[u].size();i++)
- q.push(G[u][i]);
- vis[u]=true;
- while(!q.empty())
- {
- u=q.top().vertex;
- if(vis[u]==false)
- {
- vis[u]=true;
- ans+=q.top().weight;
- //cout<<q.top().weight<<" "<<q.top().vertex<<endl;
- q.pop();
- for(i=0;i<G[u].size();i++)
- {
- v=G[u][i].vertex;
- if(vis[v]==false)
- {
- //cout<<G[u][i].weight<<" "<<v<<"push"<<endl;
- q.push(G[u][i]);
- }
- }
- }
- else
- q.pop();
- }
- return ans;
- }
- int main()
- {
- ll prev,temp,i,n,m,k,u,v,w;
- while(cin>>n)
- {
- if(f==true)
- cout<<endl;
- f=true;
- for(i=1,prev=0;i<n;i++)
- {
- cin>>temp>>temp>>temp;
- prev+=temp;
- }
- cin>>k;
- while(k--)
- {
- cin>>u>>v>>w;
- G[u].push_back(edge(v,w));
- G[v].push_back(edge(u,w));
- }
- cin>>m;
- for(i=0;i<m;i++)
- {
- cin>>u>>v>>w;
- G[u].push_back(edge(v,w));
- G[v].push_back(edge(u,w));
- }
- cout<<prev<<endl<<prim()<<endl;
- for(i=1;i<=n;i++)
- {
- vis[i]=false;
- G[i].clear();
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement