fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct node
  4. {
  5.     int data,weight;
  6.     node *next;
  7. };
  8. struct rnode
  9. {
  10.     int count;
  11.     node *next;
  12. }*a;
  13. int ans,n;
  14.  
  15. int dfs(int start,int v[],int c[])
  16. {
  17.  
  18.     node *t;
  19.     t=a[start].next;
  20.     int curr=t->data;
  21.     int cw=t->weight;
  22.  
  23.     while(t!=NULL)
  24.     {
  25.         cw=t->weight;
  26.         curr=t->data;
  27.         if(v[curr]==0)
  28.         {
  29.             v[curr]=1;
  30.             c[start]+=dfs(curr,v,c);
  31.         }
  32.         t=t->next;
  33.     }
  34.     c[start]+=1;
  35.     int x=c[start];
  36.     int y=n-x;
  37.  
  38.     ans+=(2*min(x,y)*cw);
  39.     return c[start];
  40.  
  41. }
  42. int main()
  43. {
  44.     int t;
  45.     cin>>t;
  46.     for(int j=1;j<=t;j++)
  47.     {
  48.         cin>>n;
  49.         a=new rnode[n+1];
  50.         for(int i=1;i<=n;i++)
  51.         {
  52.             a[i].next=NULL;
  53.             a[i].count=0;
  54.         }
  55.         for(int i=1;i<n;i++)
  56.         {
  57.             int x,y,z;
  58.             cin>>x>>y>>z;
  59.             node *t1,*t2;
  60.             t1=new node;
  61.             t2=new node;
  62.             t1->data=y;
  63.             t1->weight=z;
  64.             t2->data=x;
  65.             t2->weight=z;
  66.             t1->next=a[x].next;
  67.             a[x].next=t1;
  68.             a[y].count+=1;a[x].count+=1;
  69.             t2->next=a[y].next;
  70.             a[y].next=t2;
  71.         }
  72.  
  73.         int s=0,v[n+1]={};
  74.         int c[n+1]={};
  75.         for(int i=1;i<=n;i++)
  76.         {
  77.             if(a[i].count==1)
  78.             {
  79.                 s=i;
  80.                 break;
  81.             }
  82.         }
  83.  
  84.         v[s]=1;
  85.         int co=dfs(s,v,c);
  86.         cout<<"Case #"<<j<<": "<<ans<<endl;
  87.         n=0;ans=0;
  88.         delete []a;
  89.  
  90.     }
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 4200KB
comments (?)
stdin
copy 
2
4
1 2 3
2 3 2
4 3 2
6
1 2 3
2 3 4
2 4 1
4 5 8
5 6 5
stdout
copy 
Case #1: 18
Case #2: 62
https://ideone.com/ODOFBt
problem HOLI, based on SPOJ submission 26085711 (CPP), 2020-06-02 18:45:29
language:
C++ (gcc 8.3)
created:
3 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!