Source code for submission s1043

Go to diff to previous submission

fr.cpp

  1. #include <cstdio>
  2. #include <vector>
  3. #include <climits>
  4. using namespace std;
  5.  
  6. struct Node
  7. {
  8. 	int num;
  9. 	vector<int> children;
  10.  
  11. 	Node( int n = 0 )
  12. 	{
  13. 		num = n;
  14. 	}
  15.  
  16. 	void add( int n )
  17. 	{
  18. 		children.push_back(n);
  19. 	}
  20.  
  21. 	int ccount()
  22. 	{
  23. 		return children.size();
  24. 	}
  25. };
  26.  
  27. int bublej( int ** pole, Node * node, Node ** graph, int parent )
  28. {
  29. 	if( node->ccount() == 1 && node->num != parent )
  30. 	{
  31. 		//printf( "jsem %d a vracim %d\n", node->num, node->effort );
  32. 		return pole[parent-1][node->num-1];
  33. 	}
  34.  
  35. 	int tmp = pole[parent-1][node->num-1];
  36. 	//printf( "jsem %d a prisel jsem z %d\n", node->num, parent );
  37.  
  38. 	int sum = 0;
  39. 	for( int i = 0; i < node->ccount(); i++ )
  40. 	{
  41. 		if( node->children[i] == parent )
  42. 			continue;
  43.  
  44. 		int b = bublej( pole, graph[ node->children[i]-1 ], graph, node->num );
  45.  
  46. 		//printf( "sum (%d) += %d\n", sum, b );
  47. 		sum += b;
  48. 	}
  49.  
  50. 	//printf( "jsem %d, mam %d a od deti mam %d\n", node->num, node->effort, sum );
  51. 	if( sum < tmp )
  52. 		tmp = sum;
  53.  
  54. 	pole[parent-1][node->num-1] = tmp;
  55. 	pole[node->num-1][parent-1] = tmp;
  56. 	return tmp;
  57. }
  58.  
  59. int main()
  60. {
  61. 	int ** pole = new int* [1000];
  62. 	for( int i = 0; i < 1000; i++ ) 
  63. 		pole[i] = new int[1000];
  64.  
  65. 	int nodec, center;
  66. 	while( scanf("%d %d\n", &nodec, &center) == 2 )
  67. 	{
  68. 		Node ** nodeArr = new Node*[nodec];
  69. 		for( int i = 0; i < nodec; i++ )
  70. 			nodeArr[i] = new Node(i+1);
  71.  
  72. 		pole[center-1][center-1] = INT_MAX;
  73. 		for( int i = 0; i < nodec-1; i++ )
  74. 		{
  75. 			int n,c,e;
  76. 			scanf( "%d %d %d\n", &n,&c,&e );
  77.  
  78. 			nodeArr[n-1]->add(c);
  79. 			nodeArr[c-1]->add(n);
  80. 			pole[n-1][c-1] = e;
  81. 			pole[c-1][n-1] = e;
  82. 		}
  83.  
  84. 		/*
  85. 		for( int i = 0; i < nodec; i++ )
  86. 		{
  87. 			printf( "Node%d (%d) : ", nodeArr[i]->num, nodeArr[i]->effort );
  88. 			for( int j = 0; j < nodeArr[i]->ccount(); j++ )
  89. 				printf( " %d", nodeArr[i]->children[j] );
  90. 			printf( "\n" );
  91. 		}
  92. 		*/
  93.  
  94. 		int result = bublej( pole, nodeArr[center-1], nodeArr, center );
  95. 		printf( "%d\n", result );
  96. 	}
  97.  
  98. 	return 0;
  99. }
  100.  

Diff to submission s1008

fr.cpp

--- c5.s1008.cteam031.fr.cpp.0.fr.cpp
+++ c5.s1043.cteam031.fr.cpp.0.fr.cpp
@@ -1,4 +1,5 @@
 #include <cstdio>
 #include <vector>
+#include <climits>
 using namespace std;
 
@@ -69,5 +70,5 @@
                         nodeArr[i] = new Node(i+1);
                 
-                pole[center-1][center-1] = 2000;
+                pole[center-1][center-1] = INT_MAX;
                 for( int i = 0; i < nodec-1; i++ )
                 {