fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define max 100001
  5. #define llu long long int 
  6. #define sl(a) scanf("%lld",&a)
  7. vector<llu>graph[max];
  8. bool visited[max];
  9. llu cnt=0;
  10. void dfs(llu s )
  11. {  stack<llu>S;
  12.        S.push(s);
  13.       visited[s] = true;
  14.          while(!S.empty()){ 
  15.            llu  v=S.top();
  16.              S.pop();
  17.     for(llu i=0;i<graph[v].size();i++)
  18.              if(visited[graph[v][i]] == false){
  19.                  S.push(graph[v][i]);
  20.                visited[graph[v][i]] = true; }
  21.          }
  22. }
  23. void initialize() {
  24.         for(llu i = 0;i <max;++i)
  25.          visited[i] = false; }
  26. int main() {
  27.   // freopen("aa.in","r",stdin);
  28.  //freopen("AA.out","w",stdout);
  29.     llu q;
  30.     sl(q);
  31.     for(int a0 = 0; a0 < q; a0++){
  32.         // memset(visited, false, sizeof(visited));
  33.         initialize(); 
  34.         llu n,m,x,y;
  35.         sl(n);
  36.         sl(m);
  37.         sl(x);
  38.         sl(y);
  39.  
  40.        //in >> n >> m >> x >> y;
  41.         for(llu a1 = 0; a1 < m; a1++){
  42.             llu city_1;
  43.             llu city_2;
  44.             sl(city_1);
  45.             sl(city_2);
  46.  
  47.             graph[city_1].push_back(city_2);
  48.             graph[city_2].push_back(city_1);
  49.  
  50.         }
  51.        if(y>=x)
  52.             cout<<n*x<<endl;
  53.        else
  54.        {   llu  disconnected=0,ans=0;
  55.            for(llu i=1;i<=n;i++)
  56.            {  if(visited[i] == false)
  57.                {
  58.                dfs(i );  
  59.                 disconnected++;
  60.                } 
  61.  
  62.            }
  63.               ans= (n-disconnected)*y + disconnected*x;
  64.                 cout<<ans<<endl;
  65.         for(llu i=0;i<=n;i++)
  66.                graph[i].clear();
  67.        }
  68.     }
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 17680KB
comments (?)
stdin
copy 
2
3 3 2 1
1 2
3 1
2 3
6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6
stdout
copy 
4
12
https://ideone.com/LuRZXw
language:
C++ (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!