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

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
typedef long long LL;
#define MAXN 50001 
LL dp[MAXN][21];
vector<pair<int, int> > G[MAXN];
int n, r, k;
void dfs(int u, int f)
{
    for(int i = 0; i < G[u].size(); i++)
    {
        int to = G[u][i].first;if(to == f)continue;
        int cst = G[u][i].second;
        dfs(to, u);
        for(int j = k; j >= 0; j--)
        {
            dp[u][j] += dp[to][0]+(LL)cst*2;
            for(int p = 1; p <= j; p++)
                dp[u][j] = min(dp[u][j], dp[u][j-p]+dp[to][p]+(LL)p*cst);
        }
    }
}
int main()
{
    //freopen("test_data.txt", "r", stdin);
    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 x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        G[x].push_back(make_pair(y, c));
        G[y].push_back(make_pair(x, c));
    }
    dfs(r, 0);
    printf("%lld\n", dp[r][k]);
    return 0;
}