fr.cpp
#include <cstdio>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
#define N_MAX 1004
struct node{
vector<pair<int, int> > connected;
};
int rec(vector<node> &nodes, int n, int from, int cost);
int main(){
int n, idc;
while (scanf("%d %d", &n, &idc) != EOF){
vector<node> nodes(n+1);
// nodes.reserve(N_MAX);
// bool visited[n+1];
// int costs[n+1];
int from, to, cost;
for (int i = 0; i < n - 1; i++){
scanf("%d %d %d", &from, &to, &cost);
nodes[from].connected.push_back(make_pair(to, cost));
nodes[to].connected.push_back(make_pair(from, cost));
}
printf("%d\n", rec(nodes, idc, 0, 1000*1000+10));
}
}
static inline int min(int a, int b){
return (a < b)? a : b;
}
int rec(vector<node> &nodes, int n, int from, int cost) {
if (nodes[n].connected.size() == 1 && nodes[n].connected[0].first == from) {
return nodes[n].connected[0].second;
} else {
int sum = 0;
for (vector<pair<int, int> >::iterator it = nodes[n].connected.begin();
it != nodes[n].connected.end(); ++it){
if (it->first == from){
continue;
}
sum += rec(nodes, it->first, n, it->second);
}
return min(cost, sum);
}
}