Source code for submission s899

fr.cpp

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <queue>
  7. #include <map>
  8. #include <string>
  9. #include <cmath>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13.  
  14. #include <stdio.h>
  15. #include <ctype.h>
  16. #include <math.h>
  17. #include <string.h>
  18. #include <stdlib.h>
  19.  
  20. using namespace std;
  21.  
  22. #define X first
  23. #define Y second
  24. #define MP make_pair
  25. #define PB push_back
  26. #define SZ size
  27.  
  28. int main () {
  29. vector<pair <int, int> > sused;
  30. int hodnota[1005];
  31. int pom[1005], pom2[1005];
  32. int hrany[1005][1005];
  33. int sus[1005][1005];
  34. queue<int> t;
  35.  
  36. int i, ii, n, koren, a, b, c;
  37. while (scanf("%d %d", &n, &koren) > 0) {
  38. for (i = 1; i < 1002; i++) {
  39. pom[i] = 0;
  40. hodnota[i] = 0;
  41. }
  42. for (i = 1; i < 1002; i++) {
  43. for (ii = 1; ii < 1002; ii++) {
  44. hrany[i][ii] = 0;
  45. }
  46. }
  47. for (i = 0; i < n - 1; i++) {
  48. scanf("%d %d %d", &a, &b, &c);
  49. pom[a] = pom[a] + 1;
  50. pom[b] = pom[b] + 1;
  51. //cout << pom[1] << endl;
  52. hrany[a][b] = c;
  53. hrany[b][a] = c;
  54. sus[a][pom[a] - 1] = b;
  55. sus[b][pom[b] - 1] = a;
  56. pom2[a] = pom2[a] + 1;
  57. pom2[b] = pom2[b] + 1;
  58. }
  59. for (i = 1; i <= n; i++) {
  60. sused.PB(MP(pom[i], i));
  61. }
  62. sort(sused.begin(), sused.end());
  63. for (i = 1; i <= n; i++) {
  64. if (pom[i] == 1)
  65. t.push(i);
  66. }
  67. while(!t.empty()) {
  68. n = t.front();
  69. t.pop();
  70.  
  71. //cout << n << "aaa" << pom[1] << endl;
  72. for (ii = 0; ii < pom[n]; ii++) {
  73.  
  74. //cout << sus[n][ii] << "bbb" << endl;
  75. if (hodnota[n] == 0 || hodnota[n] > hrany[n][sus[n][ii]])
  76. hodnota[sus[n][ii]] = hodnota[sus[n][ii]] + hrany[n][sus[n][ii]];
  77. else
  78. hodnota[sus[n][ii]] = hodnota[sus[n][ii]] + hodnota[n];
  79. pom2[sus[n][ii]]--;
  80. if (pom2[sus[n][ii]] == 1)
  81. t.push(sus[n][ii]);
  82. //cout << sus[n][ii] << " " << hodnota[sus[n][ii]] << " " << n << endl;
  83. }
  84. pom2[n] = -1;
  85. }
  86. cout << hodnota[koren] << endl;
  87. sused.clear();
  88. }
  89. return 0;
  90. }
  91.