记录编号	350330	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	树和机器人	最终得分	100
用户昵称	srO cwm Orz	是否通过	通过
代码语言	C++	运行时间	0.651 s
提交时间	2016-11-15 18:38:17	内存使用	9.90 MiB

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 50010;

typedef long long ll;
int n,r,k;
long long dp[maxn][25];
struct Edge{
	int from,to,dist;
};
vector<int> G[maxn];
vector<Edge> edges;

void addEdge(int u,int v,int w){
	edges.push_back((Edge){u,v,w});
	edges.push_back((Edge){v,u,w});
	int m = edges.size();
	G[u].push_back(m-2);
	G[v].push_back(m-1);
}
void dfs(int u,int v){
	for(int i = 0; i < G[v].size(); i++){
		Edge &e = edges[G[v][i]];
		if(e.to == u)continue;
		dfs(v,e.to);
		for(int j = k; j >= 0; j--){
			dp[v][j] += dp[e.to][0] + (ll)(e.dist<<1);
			for(int l = 1; l <= j; l++)
				dp[v][j] = min(dp[v][j], dp[v][j-l] + dp[e.to][l] + (ll)e.dist*l);
		}
	}
}
int main()
{
	#ifndef DEBUG
		string FileName="trobot";
		freopen((FileName+".in").c_str(),"r",stdin);
		freopen((FileName+".out").c_str(),"w",stdout);
	#endif
	scanf("%d%d%d",&n,&r,&k);
	for(int i = 1; i < n; i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addEdge(u,v,w);
	}
	dfs(-1,r);
	printf("%I64d",dp[r][k]);
}