记录编号	350048	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	树和机器人	最终得分	100
用户昵称	Riolu	是否通过	通过
代码语言	C++	运行时间	0.565 s
提交时间	2016-11-15 15:23:21	内存使用	11.19 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=5e4+10;

struct Edge{
	int to,ne,v;
	Edge() {}
	Edge(int to_,int ne_,int v_) { to = to_, ne = ne_, v = v_; }
} e[maxn << 1];
int head[maxn],ecnt;
inline void add_edge(int fr, int to, int v) {
	e[++ecnt]=Edge(to,head[fr],v), head[fr]=ecnt;
	e[++ecnt]=Edge(fr,head[to],v), head[to]=ecnt;
}
int n,r,k;
long long dp[maxn][25];
inline void read() {
	scanf("%d%d%d",&n,&r,&k);
	int fr,to,v,i;
	for (i=1;i<n;i++) {
		scanf("%d%d%d",&fr,&to,&v);
		add_edge(fr,to,v);
	}
}
void dfs(int now,int fr){
	for (int i=head[now];i;i=e[i].ne){
		int to=e[i].to;
		if(to==fr) continue;
		dfs(to,now);
		for (int j=k;j>=0;j--){
			dp[now][j]+=dp[to][0]+1ll*2*e[i].v;
			for(int t=1;t<=j;t++)
				dp[now][j]=min(dp[now][j],dp[now][j-t]+dp[to][t]+1ll*t*e[i].v);
		}
	}
}
int main(){
	freopen("trobot.in","r",stdin);
	freopen("trobot.out","w",stdout);
	read();
	dfs(r,-1);
	printf("%lld\n", dp[r][k]);
	return 0;
}