Source code for submission s968

Go to diff to previous submission

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct TNode{
	int m_Number;
	int m_Effort;
	vector<TNode *> m_Child;
	TNode(int number, int effort){
		m_Number = number;
		m_Effort = effort;
	}
};
 
TNode * SearchNode(int number, TNode * node){
	if(node->m_Number == number){
		return node;
	}
	if(node->m_Child.empty()){
		return NULL;
	}
	TNode * child;
	for(vector<TNode*>::iterator it = node->m_Child.begin(); it != node->m_Child.end(); ++it){
		child = SearchNode(number, *it);
		if(child){
			break;
		}
	}
	return child;
}
 
int GetMin(TNode * node){
	if(node->m_Child.empty()){
		return node->m_Effort;
	}
	int minChildren = 0;
	for(vector<TNode*>::iterator it = node->m_Child.begin(); it != node->m_Child.end(); ++it){
		minChildren += GetMin((*it));
	}
	if(minChildren < (node->m_Effort)){
		return minChildren;
	}
	else{
		return node->m_Effort;
	}
}
 
int main(void){
	int numOfNodes, central;
	while(cin >> numOfNodes >> central){
		TNode * root = new TNode(central, 0);
		/*for(int i = 1; i < numOfNodes; i++){
			int number1, number2, effort;
			TNode * node1, * node2;
			cin >> number1 >> number2 >> effort;
			node1 = SearchNode(number1, root);
			node2 = SearchNode(number2, root);
			if(node1){
				node2 = new TNode(number2, effort);
				node1->m_Child.push_back(node2);
			}
			else{
				node1 = new TNode(number1, effort);
				node2->m_Child.push_back(node1);
			}
		}*/
		int ** table = new int * [numOfNodes];
		for(int i = 0; i < numOfNodes; i++){
			table[i] = new int [numOfNodes];
			for(int j = 0; j < numOfNodes; j++){
				table[i][j] = -1;
			}
		}
		for(int i = 1; i < numOfNodes; i++){
			int num1, num2, effort;
			cin >> num1 >> num2 >> effort;			
			table[num1-1][num2-1] = effort;
			table[num2-1][num1-1] = effort;
		}
		queue<int> nodes;
		nodes.push(central);
		while(!nodes.empty()){
			int i = nodes.front();
			TNode * node = SearchNode(i, root);
			for(int j = 0; j < numOfNodes; j++){
				int effort = table[i-1][j];
				table[j][i-1] = -1;
				if(effort > -1){
					node->m_Child.push_back(new TNode(j+1, effort));
					nodes.push(j+1);
				}
			}
			nodes.pop();
		}
		int min = 0;
		for(vector<TNode*>::iterator it = root->m_Child.begin(); it != root->m_Child.end(); ++it){
			min += GetMin(*it);
		}
		cout << min << endl;
	}
	return 0;
}
 
 
 
 

Diff to submission s780

--- c5.s780.cteam009.fr.cpp.0.fr.cpp
+++ c5.s968.cteam009.fr.cpp.0.fr.cpp
@@ -2,4 +2,5 @@
 #include <iostream>
 #include <vector>
+#include <queue>
 using namespace std;
 
@@ -51,5 +52,5 @@
         while(cin >> numOfNodes >> central){
                 TNode * root = new TNode(central, 0);
-                for(int i = 1; i < numOfNodes; i++){
+                /*for(int i = 1; i < numOfNodes; i++){
                         int number1, number2, effort;
                         TNode * node1, * node2;
@@ -65,5 +66,33 @@
                                 node2->m_Child.push_back(node1);
                         }
-                }       
+                }*/
+                int ** table = new int * [numOfNodes];
+                for(int i = 0; i < numOfNodes; i++){
+                        table[i] = new int [numOfNodes];
+                        for(int j = 0; j < numOfNodes; j++){
+                                table[i][j] = -1;
+                        }
+                }
+                for(int i = 1; i < numOfNodes; i++){
+                        int num1, num2, effort;
+                        cin >> num1 >> num2 >> effort;                  
+                        table[num1-1][num2-1] = effort;
+                        table[num2-1][num1-1] = effort;
+                }
+                queue<int> nodes;
+                nodes.push(central);
+                while(!nodes.empty()){
+                        int i = nodes.front();
+                        TNode * node = SearchNode(i, root);
+                        for(int j = 0; j < numOfNodes; j++){
+                                int effort = table[i-1][j];
+                                table[j][i-1] = -1;
+                                if(effort > -1){
+                                        node->m_Child.push_back(new TNode(j+1, effort));
+                                        nodes.push(j+1);
+                                }
+                        }
+                        nodes.pop();
+                }
                 int min = 0;
                 for(vector<TNode*>::iterator it = root->m_Child.begin(); it != root->m_Child.end(); ++it){