Go to diff to previous submission
#include <iostream> #include <cstdio> #include <vector> #include <limits> using namespace std; struct node { vector<int> edges; vector<int> weights; bool used; int cost_to_disable; }; int mainRoot; int compute(vector<node>& nodes, int root) { //cout << "@@@JSEM V" << root << " velikost:" << nodes[root].edges.size() << endl; nodes[root].used = true; if(nodes[root].edges.size() == 1 && root != mainRoot) return 1001; int min = 0; for(int i = 0; i < nodes[root].edges.size(); ++i) { // cout << "root" << root << " i" << i << " KOUKAM NA NODE:" << nodes[root].edges[i] << endl; if(!nodes[nodes[root].edges[i]].used) { int costToDisable; //nodes[nodes[root].edges[i]].used = true; costToDisable = compute(nodes, nodes[root].edges[i]); // cout << "JSEM V" << root << " i:" << i << " min:" << min << " CTD:" << costToDisable << " weights:" << nodes[root].weights[i] << endl; if(costToDisable > nodes[root].weights[i]) costToDisable = nodes[root].weights[i]; min += costToDisable; } } //cout << "RETURNING MIN: " << min << endl; return min; } int main() { int nodeCount; while(scanf("%d %d", &nodeCount, &mainRoot) > 0) { vector<node> nodes(nodeCount + 1); for(int i = 0; i < nodeCount - 1; ++i) { int from, to, weight; scanf("%d %d %d", &from, &to, &weight); nodes[from].edges.push_back(to); nodes[from].weights.push_back(weight); nodes[to].edges.push_back(from); nodes[to].weights.push_back(weight); nodes[from].used = false; nodes[to].used = false; } cout << compute(nodes, mainRoot) << endl; } }
--- c5.s860.cteam052.fr.cpp.0.fr.cpp +++ c5.s942.cteam052.fr.cpp.0.fr.cpp @@ -16,5 +16,6 @@ int compute(vector<node>& nodes, int root) { - //cout << root << " " << nodes[root].edges.size() << endl; + //cout << "@@@JSEM V" << root << " velikost:" << nodes[root].edges.size() << endl; + nodes[root].used = true; if(nodes[root].edges.size() == 1 && root != mainRoot) return 1001; @@ -22,9 +23,11 @@ for(int i = 0; i < nodes[root].edges.size(); ++i) { + // cout << "root" << root << " i" << i << " KOUKAM NA NODE:" << nodes[root].edges[i] << endl; if(!nodes[nodes[root].edges[i]].used) { int costToDisable; - nodes[nodes[root].edges[i]].used = true; + //nodes[nodes[root].edges[i]].used = true; costToDisable = compute(nodes, nodes[root].edges[i]); + // cout << "JSEM V" << root << " i:" << i << " min:" << min << " CTD:" << costToDisable << " weights:" << nodes[root].weights[i] << endl; if(costToDisable > nodes[root].weights[i]) costToDisable = nodes[root].weights[i]; @@ -32,5 +36,5 @@ } } - + //cout << "RETURNING MIN: " << min << endl; return min; }