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

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 5e4 + 10;
int n, s, m;
int head[maxn], edge_num;
int f[maxn][22];

struct Edge {
	int next, to, dis;
}edge[maxn << 1];

int read();
void add_edge(int, int, int);
void dfs(int, int);

int main() {
	freopen("trobot.in", "r", stdin);
	freopen("trobot.out", "w", stdout);
	int i;
	n = read(), s = read(), m = read();
	for(i = 1; i < n; i++) {
		int u = read(), v = read(), dis = read();
		add_edge(u, v, dis);
		add_edge(v, u, dis);
	}
	dfs(s, 0);
	cout << f[s][m] << "\n";
	return 0;
}

void dfs(int now, int father) {
	int i, j, k;
	for(i = head[now]; i; i = edge[i].next) {
		int to = edge[i].to;
		int dis = edge[i].dis;
		if(to == father) continue;
		dfs(to, now);
		for(j = m; j >= 0; j--) {
			f[now][j] += f[to][0] + (dis << 1);
			for(k = 1; k <= j; k++)
				f[now][j] = min(f[now][j], f[now][j - k] + f[to][k] + k*dis);
		}
	}
}

void add_edge(int from, int to, int dis) {
	edge[++edge_num].next = head[from];
	edge[edge_num].to = to;
	edge[edge_num].dis = dis;
	head[from] = edge_num;
}

int read() {
	char s = getchar();
	int t = 0, f = 1;
	while(!isdigit(s)) {
		if(s == '-') f = -1;
		s = getchar();
	}
	while(isdigit(s)) {
		t = (t << 3) + (t << 1) + s - '0';
		s = getchar();
	}
	return t*f;
}