fork(4) download
copy 
  1. #include <cstdio>
  2. #include<algorithm>
  3. #include <cstring>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. const int maxN = 100010;
  8. vector<int> a[maxN];
  9. vector<int> x;
  10. int mark[maxN];
  11. int value[maxN];
  12. int mini=10000000;
  13.  
  14. void dfs(int u)
  15. {
  16.     mark[u]=1;
  17. 	if(value[u] < mini && value[u]>=0)
  18. 	mini= value[u];
  19.  
  20. 	for(int i=a[u].size();i--;)
  21. 	{
  22. 		int v=a[u][i];
  23. 		if(!mark[v]) dfs(v);
  24. 	}
  25. }
  26.  
  27. int main()
  28. {
  29. 		int n,m,flag=0,minx=0;
  30. 		scanf("%d%d",&n,&m);
  31.  
  32. 		int i,u,v;
  33. 		long long sum=0;
  34. 		for(i=0;i<n;i++) {
  35. 		    a[i].clear();
  36. 		    mark[i]=0;
  37. 		}
  38. 		for(int k=0;k<m;k++)
  39. 		{
  40. 			scanf("%d%d",&u,&v);
  41. 			a[u-1].push_back(v-1);
  42. 			a[v-1].push_back(u-1);
  43. 		}
  44. 		for(i=0;i<n;i++) scanf("%d",&value[i]);
  45.  
  46. 		for(i=0;i<n;i++)
  47. 		{
  48. 			if(!mark[i])
  49. 			{
  50.                 mini=10000000;
  51. 				dfs(i);
  52. 				if(mini==10000000)
  53. 				flag=1;
  54. 				else
  55.                 x.push_back(mini);
  56. 			}
  57. 		}
  58.  
  59.         if(flag==1)
  60.         {
  61.             printf("-1\n");
  62.         }
  63.  
  64.         if(x.size()<2)
  65.         {
  66.             printf("0\n");
  67.             return 0;
  68.         }
  69.  
  70.             for(i=0;i<x.size();i++)
  71.             {
  72.                 sum= sum+ x[i];
  73.                 if(x[i]<minx)minx= x[i];
  74.             }
  75.  
  76.             sum+= (x.size()-2)*minx;
  77.             printf("%lld\n",sum);
  78.  
  79. 	return 0;
  80. }
  81.  
  82.  
Runtime error #stdin #stdout 0s 4848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/S9DpAw
language:
C++ (gcc 8.3)
created:
10 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!