Go to diff to previous submission
#include <string.h> #include <stdio.h> #include <set> #include <map> #include <algorithm> using namespace std; typedef struct { map<int, int> post; // <node, cena> } mynode; void vypis(set<int> &u) { printf("pouzite: "); for (set<int>::iterator it=u.begin(); it != u.end(); it++) { printf("%d ", *it); } printf("\n"); } int dotcena(mynode &g, set<int> &u, mynode *gr, bool nieSomCentrum) { if (g.post.size() == 1 && nieSomCentrum) { return 2000000; } int acc = 0; int oldAcc; for (map<int,int>::iterator it=g.post.begin(); it != g.post.end(); it++) { // vypis(u); if (u.find(it->first) == u.end()) { u.insert(it->first); oldAcc = acc; acc += min(it->second, dotcena(gr[it->first], u, gr, true)); //printf("idem na %d s cenou %d, sec = %d \n", it->first, acc - oldAcc, it->second); } } return acc; }; int main() { int n, c; int i; int u, v, w; int v1, v2; while (true) { if ((scanf("%d %d\n", &n, &c) < 2)) return 0; mynode graf[1100]; set<int> used; used.insert(c); if (n == 2) { scanf("%d %d %d\n", &u, &v, &w); printf("%d\n", w); } else { for (i = 0; i < n - 1; i++) { scanf("%d %d %d\n", &u, &v, &w); graf[u].post[v] = w; graf[v].post[u] = w; //printf("%d %d\n", graf[u].post[v], graf[v].post[u]); } printf("%d\n", dotcena(graf[c], used, graf, false)); } } return 0; }
--- c5.s1037.cteam082.fr.cpp.0.fr.cpp +++ c5.s1044.cteam082.fr.cpp.0.fr.cpp @@ -19,6 +19,6 @@ } -int dotcena(mynode &g, set<int> &u, mynode *gr) { - if (g.post.size() == 1) { return 2000000; } +int dotcena(mynode &g, set<int> &u, mynode *gr, bool nieSomCentrum) { + if (g.post.size() == 1 && nieSomCentrum) { return 2000000; } int acc = 0; int oldAcc; @@ -28,5 +28,5 @@ u.insert(it->first); oldAcc = acc; - acc += min(it->second, dotcena(gr[it->first], u, gr)); + acc += min(it->second, dotcena(gr[it->first], u, gr, true)); //printf("idem na %d s cenou %d, sec = %d \n", it->first, acc - oldAcc, it->second); } @@ -62,5 +62,5 @@ } - printf("%d\n", dotcena(graf[c], used, graf)); + printf("%d\n", dotcena(graf[c], used, graf, false)); } }