Go to diff to previous submission
#include <cstdio> #include <vector> using namespace std; struct Node { int num; vector<int> children; Node( int n = 0 ) { num = n; } void add( int n ) { children.push_back(n); } int ccount() { return children.size(); } }; int bublej( int ** pole, Node * node, Node ** graph, int parent ) { if( node->ccount() == 1 && node->num != parent ) { //printf( "jsem %d a vracim %d\n", node->num, node->effort ); return pole[parent-1][node->num-1]; } int tmp = pole[parent-1][node->num-1]; //printf( "jsem %d a prisel jsem z %d\n", node->num, parent ); int sum = 0; for( int i = 0; i < node->ccount(); i++ ) { if( node->children[i] == parent ) continue; int b = bublej( pole, graph[ node->children[i]-1 ], graph, node->num ); //printf( "sum (%d) += %d\n", sum, b ); sum += b; } //printf( "jsem %d, mam %d a od deti mam %d\n", node->num, node->effort, sum ); if( sum < tmp ) tmp = sum; pole[parent-1][node->num-1] = tmp; pole[node->num-1][parent-1] = tmp; return tmp; } int main() { int ** pole = new int* [1000]; for( int i = 0; i < 1000; i++ ) pole[i] = new int[1000]; int nodec, center; while( scanf("%d %d\n", &nodec, ¢er) == 2 ) { Node ** nodeArr = new Node*[nodec]; for( int i = 0; i < nodec; i++ ) nodeArr[i] = new Node(i+1); pole[center-1][center-1] = 2000; for( int i = 0; i < nodec-1; i++ ) { int n,c,e; scanf( "%d %d %d\n", &n,&c,&e ); nodeArr[n-1]->add(c); nodeArr[c-1]->add(n); pole[n-1][c-1] = e; pole[c-1][n-1] = e; } /* for( int i = 0; i < nodec; i++ ) { printf( "Node%d (%d) : ", nodeArr[i]->num, nodeArr[i]->effort ); for( int j = 0; j < nodeArr[i]->ccount(); j++ ) printf( " %d", nodeArr[i]->children[j] ); printf( "\n" ); } */ int result = bublej( pole, nodeArr[center-1], nodeArr, center ); printf( "%d\n", result ); } return 0; }
--- c5.s991.cteam031.fr.cpp.0.fr.cpp +++ c5.s1008.cteam031.fr.cpp.0.fr.cpp @@ -26,5 +26,5 @@ int bublej( int ** pole, Node * node, Node ** graph, int parent ) { - if( node->ccount() == 1 ) + if( node->ccount() == 1 && node->num != parent ) { //printf( "jsem %d a vracim %d\n", node->num, node->effort );