Source code for submission s1044

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

Diff to submission s1037

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