Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #define MAXN 1001
  4. #define INFTY 100000000
  5.  
  6. using namespace std;
  7.  
  8. struct edge{
  9.   int b, w;
  10. };
  11. vector<edge> G[MAXN];
  12. //vector<edge> G[MAXN];
  13. //vector<vector<edge> > G;
  14. //edge G[MAXN][MAXN];
  15. int visited[MAXN];
  16. int size[MAXN];
  17. int parent[MAXN];
  18. int LOL, r;
  19.  
  20. int min(int x, int y){
  21.   return (x > y) ? y : x;
  22. }
  23.  
  24. int stuff(){
  25.   cout << "1000 1\n";
  26.  
  27.   for( int i = 1; i < 1000; ++i ){
  28.      cout << i << " " << i + 1 << " 1000\n";
  29.   }
  30.   cout << "0 0";
  31. }
  32.  
  33. int go(int curr){
  34.   int ret;
  35.  
  36.   int sum = 0;
  37.   //++LOL;
  38.   //cout << "deb: go( " << curr << ")\n";
  39.  
  40.   if( size[curr] == 1 && curr != r ) //jestem lisciem >.<
  41.     return INFTY;
  42.  
  43.   for( int i = 0; i < size[curr]; ++i ){
  44.     if( G[curr][i].b == parent[curr] ) continue;
  45.     //cout << "list: " << i << " b= " << G[curr][i].b << " w= " << G[curr][i].w << "  [curr: " << curr << "]\n";
  46.     parent[G[curr][i].b] = curr;
  47.     ret = go( G[curr][i].b);
  48.     if( ret == INFTY ){
  49.       sum += G[curr][i].w;
  50.     }else{
  51.       sum += min(ret, G[curr][i].w );
  52.     }
  53.   }
  54.  
  55.   return sum;
  56. }
  57.  
  58. int main(){
  59.   int n, a, b, w;
  60.   edge tmp;
  61.  
  62.   ios_base::sync_with_stdio(0);
  63.   cin >> n >> r;
  64.  
  65.   //vector<vector<edge> > G;
  66.  
  67.   //for(int i = 0; i <= n; ++i) G.push_back( vector<edge>() );
  68.   //G.reserve(n+2);
  69.  
  70.   while( true ){
  71.     cin >> a >> b;
  72.    
  73.     if( a == 0 && b == 0 )
  74.       break;
  75.    
  76.     cin >> w;
  77.     tmp.b = b;
  78.     tmp.w = w;
  79.     //cout << "EDGE " << a << " <-> " << b << " w: " << w << "\n";
  80.     //G[a][size[a]] = tmp;
  81.     G[a].push_back( tmp );
  82.     ++size[a];
  83.    
  84.     tmp.b = a;
  85.     tmp.w = w;
  86.    
  87.     //G[b][size[b]] = tmp;
  88.     G[b].push_back( tmp );
  89.     ++size[b];
  90.   }
  91.  
  92.   cout << go( r);
  93.  //stuff();a.cpp:86:27: error: no match for ‘operator*’ in ‘*G’
  94.  
  95.   //cout << "\n" << LOL;
  96.  
  97.   return 0;
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement