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 ) { //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.s957.cteam031.fr.cpp.0.fr.cpp +++ c5.s991.cteam031.fr.cpp.0.fr.cpp @@ -6,13 +6,9 @@ { int num; - int effort; - int min; vector<int> children; - int parent; - Node( int n = 0, int p = 0 ) + Node( int n = 0 ) { num = n; - parent = p; } @@ -62,4 +58,8 @@ 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 ) @@ -68,10 +68,6 @@ 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++ ) { @@ -79,9 +75,4 @@ 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);