记录编号	349840	评测结果	AAAAAAAAAAAATTTTTTTT
题目名称	树和机器人	最终得分	60
用户昵称	残星噬月	是否通过	未通过
代码语言	C++	运行时间	8.081 s
提交时间	2016-11-15 12:05:40	内存使用	1.28 MiB

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 10010;
const int MAX_K = 15;

int n, root, total, K;
int head[MAX_N];
ll dp[MAX_N][MAX_K];

struct Edge {
    int v, w, next;
}edge[MAX_N * 2];

void AddEdge(int u, int v, int w)
{
    edge[total].v = v;
    edge[total].w = w;
    edge[total].next = head[u];
    head[u] = total++;
}

void wyr(int u, int p)
{
    for (int id = head[u]; id != -1; id = edge[id].next) {
        int v = edge[id].v, w = edge[id].w;
        if (v == p) continue;
        wyr(v, u);
        for (int i = K; i >= 0; --i) {
            dp[u][i] += dp[v][0] + 2 * w;
            for (int j = 1; j <= i; ++j) {
                dp[u][i] = min(dp[u][i], dp[v][j] + dp[u][i - j] + j * w);
            }
        }
    }
}

int main()
{   
    freopen("trobot.in","r",stdin);
     freopen("trobot.out","w",stdout);
    while (~scanf("%d%d%d", &n, &root, &K)) {
        memset(head, -1, sizeof(head));
        total = 0;
        for (int i = 1; i < n; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            AddEdge(u, v, w);
            AddEdge(v, u, w);
        }
        memset(dp, 0, sizeof(dp));
        wyr(root, -1);
        printf("%lld\n", dp[root][K]);
    }
    return 0;
}