记录编号	350302	评测结果	AWWWWWWWWWWWWWWWWWWW
题目名称	树和机器人	最终得分	5
用户昵称	Smile	是否通过	未通过
代码语言	C++	运行时间	0.517 s
提交时间	2016-11-15 18:04:38	内存使用	10.42 MiB

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn = 50010;
vector<pair<int,int> > G[maxn];
int n,r,k;
long long dp[maxn][25];

void addEdge(int u,int v,int w){
	G[u].push_back(make_pair(v,w));
	G[v].push_back(make_pair(u,w));
}
void dfs(int now, int fr){
	for(int i = 0; i < G[now].size(); i++){
		int to = G[now][i].first;
		if(to == fr)continue;
		dfs(to,now);
		for(int now_use = k; now_use >= 0; now_use--){
			dp[now][now_use] += dp[now][0]+G[now][i].second*2;
			for(int to_use = 1; to_use <= now_use; to_use++){
				dp[now][now_use] = min(dp[now][now_use],dp[now][now_use-to_use]+dp[to][to_use]+G[now][i].second*to_use);				
			}
		}	
	}	
}
int main() {
	freopen("trobot.in", "r", stdin);
	freopen("trobot.out", "w", stdout);
	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(r,-1);
	printf("%lld",dp[r][k]);
}