Source code for submission s1149

fr.c

  1. #include <stdio.h>
  2. #include <string.h>
  3. #define MAX 1010
  4.  
  5. char matrix[MAX][MAX] = {{0}};
  6. int children[MAX][MAX] = {{0}};
  7. int parents[MAX] = {0};
  8. int weights[MAX] = {0};
  9. int no_children[MAX] = {0};
  10. int n = 0, c = 0, i = 0, j = 0, k = 0, w, pi;
  11.  
  12. void construct(int node) {
  13. int i;
  14. for(i=0; i<MAX; i++) {
  15. if(matrix[node][i] > 0) {
  16. parents[i] = node;
  17. children[node][no_children[node]] = i;
  18. no_children[node]++;
  19. weights[i] = matrix[i][node];
  20. matrix[i][node] = 0;
  21. construct(i);
  22. }
  23. }
  24. }
  25.  
  26. int main() {
  27.  
  28. while(1) {
  29. memset(no_children, 0, MAX);
  30.  
  31. scanf("%d %d", &n, &c);
  32.  
  33. for(i=0; i<n-1; i++) {
  34. scanf("%d %d", &j, &k);
  35. scanf("%d\n", &w);
  36. matrix[j][k] = w;
  37. matrix[k][j] = w;
  38.  
  39. }
  40. construct(c);
  41.  
  42. do {
  43. k = 0;
  44. for(i=0; i<MAX; i++) {
  45.  
  46. if(no_children[i] == 0 && weights[i] > 0) {
  47. k++; // list found?
  48. pi = parents[i];
  49.  
  50. w = 0; j = 0;
  51. while(1){
  52. if(children[pi][j] == 0) break;
  53. w += weights[children[pi][j]];
  54. no_children[j] = -1;
  55. j++;
  56. }
  57. if(w < weights[pi]) weights[pi] = w;
  58. no_children[pi] = 0;
  59. }
  60. }
  61. }while(k > 2);
  62.  
  63. j = 0; w = 0;
  64. while(1) {
  65. if(children[c][j] == 0) break;
  66. w += weights[children[c][j]];
  67. j++;
  68. }
  69. printf("%d\n", w);
  70.  
  71. if(feof(stdin)) break;
  72. }
  73. return 0;
  74. }
  75.  
  76.