fr.cpp

#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <cstdlib>
#include <map>
 
using namespace std;
 
struct Edge
{
	Edge(int _dest, int _value): dest(_dest), value(_value) { }
	int dest;
	int value;
};
 
typedef std::multimap<int, Edge*> m;
 
int count(std::multimap<int, Edge*> &connections, int nodeId, int parentId)
{
 
	std::pair<m::iterator, m::iterator> range = connections.equal_range(nodeId);
	int sum = 0, mine = 0;
	for (std::multimap<int, Edge*>::iterator it = range.first; it != range.second; ++it)
	{
		if (it->second->dest == parentId)
		{
			mine = it->second->value;
			continue;
		}
		sum += count(connections, it->second->dest, nodeId);
	}
 
	if (nodeId == parentId)
		return sum;
	if (distance(range.first, range.second) == 1)
		return mine;
	return std::min(sum, mine);
}
 
int main()
{
	int nodeCount, rootId;
	while (scanf("%d %d", &nodeCount, &rootId) == 2)
	{
		--nodeCount;
		std::multimap<int, Edge*> connections;
		while (nodeCount--)
		{
			int nodeId1, nodeId2, value;
			scanf("%d %d %d", &nodeId1, &nodeId2, &value);
			connections.insert(std::pair<int, Edge*>(nodeId1, new Edge(nodeId2, value)));
			connections.insert(std::pair<int, Edge*>(nodeId2, new Edge(nodeId1, value)));
		}
		printf("%d\n", count(connections, rootId, rootId));
		for (std::multimap<int, Edge*>::iterator it = connections.begin(); it != connections.end(); ++it)
			delete (it->second);
		connections.clear();
	}
	return 0;
}