Source code for submission s780

fr.cpp

  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. struct TNode{
  7. int m_Number;
  8. int m_Effort;
  9. vector<TNode *> m_Child;
  10. TNode(int number, int effort){
  11. m_Number = number;
  12. m_Effort = effort;
  13. }
  14. };
  15.  
  16. TNode * SearchNode(int number, TNode * node){
  17. if(node->m_Number == number){
  18. return node;
  19. }
  20. if(node->m_Child.empty()){
  21. return NULL;
  22. }
  23. TNode * child;
  24. for(vector<TNode*>::iterator it = node->m_Child.begin(); it != node->m_Child.end(); ++it){
  25. child = SearchNode(number, *it);
  26. if(child){
  27. break;
  28. }
  29. }
  30. return child;
  31. }
  32.  
  33. int GetMin(TNode * node){
  34. if(node->m_Child.empty()){
  35. return node->m_Effort;
  36. }
  37. int minChildren = 0;
  38. for(vector<TNode*>::iterator it = node->m_Child.begin(); it != node->m_Child.end(); ++it){
  39. minChildren += GetMin((*it));
  40. }
  41. if(minChildren < (node->m_Effort)){
  42. return minChildren;
  43. }
  44. else{
  45. return node->m_Effort;
  46. }
  47. }
  48.  
  49. int main(void){
  50. int numOfNodes, central;
  51. while(cin >> numOfNodes >> central){
  52. TNode * root = new TNode(central, 0);
  53. for(int i = 1; i < numOfNodes; i++){
  54. int number1, number2, effort;
  55. TNode * node1, * node2;
  56. cin >> number1 >> number2 >> effort;
  57. node1 = SearchNode(number1, root);
  58. node2 = SearchNode(number2, root);
  59. if(node1){
  60. node2 = new TNode(number2, effort);
  61. node1->m_Child.push_back(node2);
  62. }
  63. else{
  64. node1 = new TNode(number1, effort);
  65. node2->m_Child.push_back(node1);
  66. }
  67. }
  68. int min = 0;
  69. for(vector<TNode*>::iterator it = root->m_Child.begin(); it != root->m_Child.end(); ++it){
  70. min += GetMin(*it);
  71. }
  72. cout << min << endl;
  73. }
  74. return 0;
  75. }
  76.