Source code for submission s923

fr.cpp

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. struct Node {
  9. int node;
  10. unsigned int weight;
  11. Node() : node(0), weight(0) {}
  12. Node(int node, int weight) : node(node), weight(weight) {}
  13. };
  14.  
  15. typedef vector<Node> Nodes;
  16. typedef vector<Nodes> Map;
  17.  
  18. Map map;
  19. int N, C;
  20.  
  21. int search(int node, unsigned int W, int parent)
  22. {
  23. bool hasChildren = false;
  24. unsigned int effort = 0;
  25.  
  26. // compute effort
  27. for (Nodes::iterator it = map[node].begin(); it != map[node].end(); ++it) {
  28. if (it->node != parent) {
  29. hasChildren = true;
  30. //cout << "node=" << it->node << " weight=" << it->weight << endl;
  31. effort += search(it->node, it->weight, node);
  32. }
  33. }
  34.  
  35. if (!hasChildren) return W;
  36.  
  37. //cout << "current=" << W << " computed=" << effort << endl;
  38.  
  39. return W < effort ? W : effort;
  40. }
  41.  
  42. int main()
  43. {
  44. ios_base::sync_with_stdio(false);
  45. while (cin >> N >> C) {
  46. int a, b, effort;
  47. int n;
  48.  
  49. map.clear();
  50. map.resize(N + 1);
  51.  
  52. for (n = 0; n < N - 1; ++n) {
  53. cin >> a >> b >> effort;
  54.  
  55. map[a].push_back(Node(b, effort));
  56. map[b].push_back(Node(a, effort));
  57. }
  58.  
  59.  
  60. cout << search(C, 0xFFFFFFFF, 0) << "\n";
  61. }
  62.  
  63. cout.flush();
  64.  
  65. return 0;
  66. }
  67.