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; }
--- 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){