Source code for submission s613

fr.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <string.h>
  5.  
  6. #include <string>
  7. #include <map>
  8. #include <vector>
  9.  
  10. int i, j, k;
  11. int i2, j2, k2;
  12.  
  13. int count, central;
  14.  
  15. struct vertex
  16. {
  17.   std::vector<int> next;
  18.   std::vector<int> price;
  19.   bool washere;
  20.   vertex()
  21.   {
  22.     washere = false;
  23.   }
  24. };
  25.  
  26. std::vector<vertex> v;
  27.  
  28. int go(int index)
  29. {
  30.   if (v[index].washere)
  31.     return 0x7FFFFFFF;
  32.  
  33.   v[index].washere = true;
  34.  
  35.   int adjc = v[index].next.size();
  36.  
  37.   int price = 0;
  38.   bool ok = false;
  39.   for (int i = 0; i < adjc; i++)
  40.     if (!v[v[index].next[i]].washere)
  41.     {
  42.       /*printf(">%d %d %d\n", index, v[index].next[i], adjc);*/
  43.       price += std::min(v[index].price[i], go(v[index].next[i]));
  44.       ok = true;
  45.     }
  46.  
  47.   if (!ok)
  48.     return 0x7FFFFFFF;
  49.  
  50.   /*printf("-- %d %d\n", index, price);*/
  51.  
  52.   return price;
  53. }
  54.  
  55. /* ------------------------------- */
  56. int main()
  57. {
  58.   while (scanf("%d%d", &count, &central) == 2)
  59.   {
  60.     v.clear();
  61.     v.resize(count + 1);
  62.     for (i = 0; i < count-1; i++)
  63.     {
  64.       /*printf("%d..\n", i);*/
  65.       int w;
  66.       scanf("%d%d%d", &j, &k, &w);
  67.       /*printf("%d %d %d..\n", j, k, w);*/
  68.       v[j].next.push_back(k);
  69.       v[j].price.push_back(w);
  70.       v[k].next.push_back(j);
  71.       v[k].price.push_back(w);
  72.     }
  73.  
  74.     printf("%d\n", go(central));
  75.   }
  76.  
  77.   return 0;
  78. }
  79.