fr.cpp
#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) {
if (g.post.size() == 1) { 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));
//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));
}
}
return 0;
}