Go to diff to previous submission
#include <cstdio> #include <vector> using namespace std; struct Node { int num; int effort; int min; vector<int> children; int parent; Node( int n = 0, int p = 0 ) { num = n; parent = p; } 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 ) { //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 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); int ** pole = new int* [nodec]; for( int i = 0; i < nodec; i++ ) pole[i] = new int[nodec]; pole[center-1][center-1] = 2000; nodeArr[center-1]->effort = 2000; for( int i = 0; i < nodec-1; i++ ) { int n,c,e; scanf( "%d %d %d\n", &n,&c,&e ); if( c != center ) nodeArr[c-1]->effort = e; else nodeArr[n-1]->effort = 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.s843.cteam031.fr.cpp.0.fr.cpp +++ c5.s957.cteam031.fr.cpp.0.fr.cpp @@ -28,12 +28,13 @@ }; -int bublej( Node * node, Node ** graph, int parent ) +int bublej( int ** pole, Node * node, Node ** graph, int parent ) { if( node->ccount() == 1 ) { //printf( "jsem %d a vracim %d\n", node->num, node->effort ); - return 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 ); @@ -44,5 +45,5 @@ continue; - int b = bublej( graph[ node->children[i]-1 ], graph, node->num ); + int b = bublej( pole, graph[ node->children[i]-1 ], graph, node->num ); //printf( "sum (%d) += %d\n", sum, b ); @@ -51,8 +52,10 @@ //printf( "jsem %d, mam %d a od deti mam %d\n", node->num, node->effort, sum ); - if( sum < node->effort ) - node->effort = sum; + if( sum < tmp ) + tmp = sum; - return node->effort; + pole[parent-1][node->num-1] = tmp; + pole[node->num-1][parent-1] = tmp; + return tmp; } @@ -66,6 +69,9 @@ nodeArr[i] = new Node(i+1); - nodeArr[center-1]->effort = 2000; + int ** pole = new int* [nodec]; + for( int i = 0; i < nodec; i++ ) pole[i] = new int[nodec]; + pole[center-1][center-1] = 2000; + nodeArr[center-1]->effort = 2000; for( int i = 0; i < nodec-1; i++ ) { @@ -80,4 +86,6 @@ nodeArr[n-1]->add(c); nodeArr[c-1]->add(n); + pole[n-1][c-1] = e; + pole[c-1][n-1] = e; } @@ -92,5 +100,5 @@ */ - int result = bublej( nodeArr[center-1], nodeArr, 0 ); + int result = bublej( pole, nodeArr[center-1], nodeArr, center ); printf( "%d\n", result ); }