Source code for submission s689

fr.cpp

  1. #include <cstdio>
  2. #include <vector>
  3. #include <utility>
  4. #include <stack>
  5.  
  6. using namespace std;
  7.  
  8. #define N_MAX 1004
  9.  
  10. struct node{
  11. vector<pair<int, int> > connected;
  12. };
  13.  
  14. int rec(vector<node> &nodes, int n, int from, int cost);
  15.  
  16. int main(){
  17.  
  18. int n, idc;
  19.  
  20. while (scanf("%d %d", &n, &idc) != EOF){
  21. vector<node> nodes(n+1);
  22. // nodes.reserve(N_MAX);
  23.  
  24. // bool visited[n+1];
  25. // int costs[n+1];
  26.  
  27. int from, to, cost;
  28. for (int i = 0; i < n - 1; i++){
  29. scanf("%d %d %d", &from, &to, &cost);
  30. nodes[from].connected.push_back(make_pair(to, cost));
  31. nodes[to].connected.push_back(make_pair(from, cost));
  32. }
  33.  
  34. printf("%d\n", rec(nodes, idc, 0, 1000*1000+10));
  35.  
  36.  
  37. }
  38. }
  39.  
  40. static inline int min(int a, int b){
  41. return (a < b)? a : b;
  42. }
  43.  
  44. int rec(vector<node> &nodes, int n, int from, int cost) {
  45. if (nodes[n].connected.size() == 1 && nodes[n].connected[0].first == from) {
  46. return nodes[n].connected[0].second;
  47. } else {
  48. int sum = 0;
  49. for (vector<pair<int, int> >::iterator it = nodes[n].connected.begin();
  50. it != nodes[n].connected.end(); ++it){
  51. if (it->first == from){
  52. continue;
  53. }
  54. sum += rec(nodes, it->first, n, it->second);
  55. }
  56. return min(cost, sum);
  57. }
  58. }
  59.