Go to diff to previous submission
// // File: fr.cc // Author: cteam030 // // Created on October 19, 2013, 12:07 PM // #include <stdlib.h> #include <iostream> #include <string> #include <vector> using namespace std; // // // struct Node { //int id; int child; int effort; }; int getEffort(vector<Node> nodes[], int id); vector<bool> banned_ids; int main(int argc, char** argv) { size_t n, cent; while(cin >> n >> cent) { //Node nodes[n+1]; vector<Node> nodes[n+1]; for(size_t i = 1;i<n;i++) { int id,id2,eff; cin >> id >> id2 >> eff; Node n1, n2; n1.child = id2; n2.child = id; n1.effort = eff; n2.effort = eff; nodes[id].push_back(n1); nodes[id2].push_back(n2); banned_ids.push_back(false); } banned_ids.push_back(false); banned_ids.push_back(false); ///////////////////////// int res = 0; /*for(size_t i=0; i<nodes[cent].subNodes.size(); i++) { res += getEffort(nodes, nodes[cent].subNodes[i]); }*/ for(size_t i=0; i<nodes[cent].size(); i++) { banned_ids[cent] = true; res += getEffort(nodes, nodes[cent][i].child); } cout << res << "\n"; } return (0); } int getEffort(vector<Node> nodes[], int id) { int effort = -1; bool no_child = true; banned_ids[id] = true; if(nodes[id].size() <= 1){ return nodes[id][0].effort; } int res = 0; for(size_t i=0; i<nodes[id].size(); i++) { if(!banned_ids[nodes[id][i].child]) { res += getEffort(nodes, nodes[id][i].child); no_child = false; }else{ effort = nodes[id][i].effort; } } //cout << res << effort if(res < effort && !no_child) return res; else return effort; }
--- c5.s848.cteam030.fr.cpp.0.fr.cpp +++ c5.s865.cteam030.fr.cpp.0.fr.cpp @@ -23,5 +23,5 @@ }; -int getEffort(vector<Node> nodes[], int id, int effort); +int getEffort(vector<Node> nodes[], int id); vector<bool> banned_ids; @@ -60,5 +60,5 @@ for(size_t i=0; i<nodes[cent].size(); i++) { banned_ids[cent] = true; - res += getEffort(nodes, nodes[cent][i].child, nodes[cent][i].effort); + res += getEffort(nodes, nodes[cent][i].child); } @@ -69,5 +69,7 @@ } -int getEffort(vector<Node> nodes[], int id, int effort) { +int getEffort(vector<Node> nodes[], int id) { + int effort = -1; + bool no_child = true; banned_ids[id] = true; if(nodes[id].size() <= 1){ @@ -76,11 +78,16 @@ int res = 0; for(size_t i=0; i<nodes[id].size(); i++) { - if(!banned_ids[nodes[id][i].child]) - res += getEffort(nodes, nodes[id][i].child, nodes[id][i].effort); + if(!banned_ids[nodes[id][i].child]) { + res += getEffort(nodes, nodes[id][i].child); + no_child = false; + }else{ + effort = nodes[id][i].effort; + } } - if(res > effort) - return effort; - else + //cout << res << effort + if(res < effort && !no_child) return res; + else + return effort; }