fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. int bfs(int start,bool *vis,vector<int>*v,int *price)//finding the min price in a graph
  5. {                                                    //here we have several disjoint graphs
  6. 	int mini=INT_MAX;
  7. 	queue<int>qu;
  8. 	qu.push(start);
  9. 	vis[start]=true;
  10. 	while(!qu.empty())
  11. 	{
  12. 		int u=qu.front();
  13. 		qu.pop();
  14. 		mini=min(mini,price[u]);
  15. 		for(int i=0;i<v[u].size();i++)
  16. 		{
  17. 			if(!vis[v[u][i]])
  18. 			{
  19. 				qu.push(v[u][i]);
  20. 				vis[v[u][i]]=true;
  21. 			}
  22. 		}
  23. 	}
  24. 	return mini;
  25. }
  26. int main() {
  27.  
  28.    int n,m;
  29.    scanf("%d%d",&n,&m);
  30.    vector<int>v[n];
  31.    for(int i=0;i<m;i++)
  32.    {int a,b;
  33.    	scanf("%d%d",&a,&b);
  34.    	v[a-1].pb(b-1);
  35.    	v[b-1].pb(a-1);
  36.    }
  37.    int price[n];
  38.    for(int i=0;i<n;i++)
  39.    {
  40.    	scanf("%d",&price[i]);
  41.    	if(price[i]<0)
  42.    	price[i]=INT_MAX;
  43.    }
  44.    vector<int>mini;
  45.    bool vis[n];
  46.    memset(vis,false,sizeof(vis));
  47.    for(int i=0;i<n;i++)
  48.    {
  49.    	if(!vis[i])
  50.    	mini.pb(bfs(i,vis,v,price));
  51.    }
  52.    sort(mini.begin(),mini.end());
  53.    if(mini[mini.size()-1]==INT_MAX)
  54.    cout<<-1;
  55.    else{long long sum=0;
  56.    for(int i=1;i<mini.size();i++)
  57.    {
  58.    	sum+=(mini[i]+mini[0]);
  59.    }
  60.    	cout<<sum;
  61.    }
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 4212KB
comments (?)
stdin
copy 
6 1
1 2
2 9 8 0 3 5
stdout
copy 
18
https://ideone.com/OH5DYh
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!