Source code for submission s860

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 << root << " " << nodes[root].edges.size() << endl;
  19. 	if(nodes[root].edges.size() == 1 && root != mainRoot)
  20. 		return 1001;
  21. 	int min = 0;
  22. 	for(int i = 0; i < nodes[root].edges.size(); ++i)
  23. 	{
  24. 			if(!nodes[nodes[root].edges[i]].used)
  25. 			{
  26. 				int costToDisable;
  27. 				nodes[nodes[root].edges[i]].used = true;
  28. 				costToDisable = compute(nodes, nodes[root].edges[i]);
  29. 				if(costToDisable > nodes[root].weights[i])
  30. 					costToDisable = nodes[root].weights[i];
  31. 				min += costToDisable;
  32. 			}
  33. 	}
  34.  
  35. 	return min;
  36. }
  37.  
  38. int main()
  39. {
  40. 	int nodeCount;
  41.  
  42. 	while(scanf("%d %d", &nodeCount, &mainRoot) > 0)
  43. 	{
  44. 		vector<node> nodes(nodeCount + 1);
  45. 		for(int i = 0; i < nodeCount - 1; ++i)
  46. 		{
  47. 			int from, to, weight;
  48. 			scanf("%d %d %d", &from, &to, &weight);
  49. 			nodes[from].edges.push_back(to);
  50. 			nodes[from].weights.push_back(weight);
  51. 			nodes[to].edges.push_back(from);
  52. 			nodes[to].weights.push_back(weight);
  53. 			nodes[from].used = false;
  54. 			nodes[to].used = false;
  55. 		}
  56. 		cout << compute(nodes, mainRoot) << endl;
  57. 	}
  58. }
  59.  
  60.