Source code for submission s942

Go to diff to previous submission

fr.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <limits>
  5. using namespace std;
  6.  
  7. struct node
  8. {
  9. vector<int> edges;
  10. vector<int> weights;
  11. bool used;
  12. int cost_to_disable;
  13. };
  14.  
  15. int mainRoot;
  16. int compute(vector<node>& nodes, int root)
  17. {
  18. //cout << "@@@JSEM V" << root << " velikost:" << nodes[root].edges.size() << endl;
  19. nodes[root].used = true;
  20. if(nodes[root].edges.size() == 1 && root != mainRoot)
  21. return 1001;
  22. int min = 0;
  23. for(int i = 0; i < nodes[root].edges.size(); ++i)
  24. {
  25. // cout << "root" << root << " i" << i << " KOUKAM NA NODE:" << nodes[root].edges[i] << endl;
  26. if(!nodes[nodes[root].edges[i]].used)
  27. {
  28. int costToDisable;
  29. //nodes[nodes[root].edges[i]].used = true;
  30. costToDisable = compute(nodes, nodes[root].edges[i]);
  31. // cout << "JSEM V" << root << " i:" << i << " min:" << min << " CTD:" << costToDisable << " weights:" << nodes[root].weights[i] << endl;
  32. if(costToDisable > nodes[root].weights[i])
  33. costToDisable = nodes[root].weights[i];
  34.  
  35. min += costToDisable;
  36. }
  37. }
  38. //cout << "RETURNING MIN: " << min << endl;
  39. return min;
  40. }
  41.  
  42. int main()
  43. {
  44. int nodeCount;
  45.  
  46. while(scanf("%d %d", &nodeCount, &mainRoot) > 0)
  47. {
  48. vector<node> nodes(nodeCount + 1);
  49. for(int i = 0; i < nodeCount - 1; ++i)
  50. {
  51. int from, to, weight;
  52. scanf("%d %d %d", &from, &to, &weight);
  53. nodes[from].edges.push_back(to);
  54. nodes[from].weights.push_back(weight);
  55. nodes[to].edges.push_back(from);
  56. nodes[to].weights.push_back(weight);
  57. nodes[from].used = false;
  58. nodes[to].used = false;
  59. }
  60. cout << compute(nodes, mainRoot) << endl;
  61. }
  62. }
  63.  
  64.  

Diff to submission s860

fr.cpp

--- c5.s860.cteam052.fr.cpp.0.fr.cpp
+++ c5.s942.cteam052.fr.cpp.0.fr.cpp
@@ -16,5 +16,6 @@
 int compute(vector<node>& nodes, int root)
 {
-        //cout << root << " " << nodes[root].edges.size() << endl;
+        //cout << "@@@JSEM V" << root << " velikost:" << nodes[root].edges.size() << endl;
+        nodes[root].used = true;
         if(nodes[root].edges.size() == 1 && root != mainRoot)
                 return 1001;
@@ -22,9 +23,11 @@
         for(int i = 0; i < nodes[root].edges.size(); ++i)
         {
+                //      cout << "root" << root << " i" << i << " KOUKAM NA NODE:" << nodes[root].edges[i] << endl;
                         if(!nodes[nodes[root].edges[i]].used)
                         {
                                 int costToDisable;
-                                nodes[nodes[root].edges[i]].used = true;
+                                //nodes[nodes[root].edges[i]].used = true;
                                 costToDisable = compute(nodes, nodes[root].edges[i]);
+                        //      cout << "JSEM V" << root << " i:" << i << " min:" << min << " CTD:" << costToDisable << " weights:" << nodes[root].weights[i] << endl;
                                 if(costToDisable > nodes[root].weights[i])
                                         costToDisable = nodes[root].weights[i];
@@ -32,5 +36,5 @@
                         }
         }
-        
+        //cout << "RETURNING MIN: " << min << endl;
         return min;
 }