fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<map>
  4. #include<set>
  5. using namespace std;
  6.  
  7. #define max 1000001
  8.  
  9. typedef long long int ll;
  10. vector<ll> v1[max];
  11. bool visit[max];
  12. map<ll,ll> cost;
  13.  
  14. ll s1[max];
  15.  
  16. ll n,m,mincost,last=0,city;
  17.  
  18. void dfs(ll src)
  19. {
  20.  visit[src]=1;
  21.  int i;
  22.  
  23.   for(i=0;i<v1[src].size();i++)
  24.   {
  25.     if(visit[v1[src][i]]==0)
  26.      dfs(v1[src][i]);
  27.   }
  28.   city++;
  29.   if((cost[src]>=0 && mincost> cost[src])  ) 
  30.    mincost=cost[src];
  31. }
  32.  
  33. bool dfs_visit(int n)
  34. {
  35. int i;
  36.  for(i=1;i<=n;i++)
  37.  {
  38.   if(visit[i]==0)
  39.   {
  40.   city=0;
  41.    mincost=max;
  42.    dfs(i);
  43.    if(mincost==max && city<n)
  44.       {
  45.       	cout<<"-1"<<endl; return false;
  46.       }
  47.    s1[last++] = mincost;
  48.   }
  49.  }	
  50.  
  51.  return true;
  52. }
  53.  
  54. int main()
  55. {
  56. cin>>n>>m;
  57. ll a,b,i;
  58. bool iso;
  59.  
  60. for(i=1;i<=n;i++)
  61. {
  62. v1[i].clear();
  63. visit[i]=0;
  64. s1[i]=0;
  65. }
  66.  
  67. while(m--)
  68. {
  69. cin>>a>>b;
  70. v1[a].push_back(b);
  71. v1[b].push_back(a);
  72. }
  73.  
  74. for(i=1;i<=n;i++)
  75. cin>>cost[i];
  76.  
  77. iso=dfs_visit(n);
  78.  
  79. if(iso==false)
  80. return 0;
  81.  
  82. ll sum=0;
  83. mincost=max;
  84.  
  85. for(i=0;i<last;i++)
  86. {
  87. sum+= s1[i];
  88. if(mincost>s1[i])
  89.  mincost=s1[i];
  90. }
  91. //cout<<"sum is "<<sum<<endl;
  92. sum+= (last-2)*mincost;
  93. cout<<sum<<endl;
  94.  
  95. return 0;
  96. }
Success #stdin #stdout 0.01s 23944KB
comments ()
stdin
copy 
5 4
1 2
2 3
3 4
4 5
1
2
3
4
5
stdout
copy 
0
https://ideone.com/OOQUBQ
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!