Source code for submission s700

fr.cpp

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8.  
  9. #define MAX(a,b) ((a)>(b)?(a):(b))
  10. #define MIN(a,b) ((a)<(b)?(a):(b))
  11.  
  12. using namespace std;
  13.  
  14. typedef struct
  15. {
  16. int y;
  17. int e;
  18. } edge;
  19.  
  20. vector< vector<edge> > G;
  21. bool marked[1002];
  22.  
  23. int dfs(int v)
  24. {
  25. marked[v] = true;
  26. int effort = 0;
  27. for(int i=0; i<G[v].size(); i++)
  28. {
  29. edge e = G[v][i];
  30. if(marked[e.y])
  31. continue;
  32. int eff = dfs(e.y);
  33. eff = MIN(e.e, eff);
  34. effort += eff;
  35. }
  36. if(effort == 0)
  37. return 9000000;
  38. return effort;
  39. }
  40.  
  41. int main()
  42. {
  43. int n, c;
  44. while(scanf("%d %d", &n, &c) == 2)
  45. {
  46. vector<edge> p;
  47. G = vector< vector<edge> >(n+1,p);
  48. for(int i=0; i<n+1; i++)
  49. marked[i] = false;
  50. for(int i=0; i<n-1; i++)
  51. {
  52. int x, y;
  53. edge e;
  54. scanf("%d %d %d", &x, &y, &e.e);
  55. e.y = y;
  56. G[x].push_back(e);
  57. e.y = x;
  58. G[y].push_back(e);
  59. }
  60. printf("%d\n", dfs(c));
  61. }
  62.  
  63. return 0;
  64. }
  65.