1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define maxn 10010 #define maxm 11 #define INF 1000000000 #define gc getchar using namespace std;
int read() { int x = 0; char c = gc(); while (!isdigit(c)) c = gc(); while (isdigit(c)) x = x * 10 + c - '0', c = gc(); return x; }
int n, s, m;
struct Edge { int to, next, w; } e[maxn * 2]; int c1, head[maxn]; inline void add_edge(int u, int v, int w) { e[c1].to = v; e[c1].w = w; e[c1].next = head[u]; head[u] = c1++; }
int f[maxn][maxm]; void dfs(int u, int fa) { for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to, w = e[i].w; if (v == fa) continue; dfs(v, u); for (int j = m; j >= 0; --j) { f[u][j] += f[v][0] + 2 * w; for (int k = 1; k <= j; ++k) f[u][j] = min(f[u][j], f[u][j - k] + f[v][k] + k * w); } } }
void init() { memset(head, -1, sizeof head); c1 = 0; memset(f, 0, sizeof f); }
void work() { init(); for (int i = 1; i < n; ++i) { int x = read(), y = read(), z = read(); add_edge(x, y, z); add_edge(y, x, z); } dfs(s, 0); cout << f[s][m] << endl; }
int main() { while (cin >> n >> s >> m) work(); return 0; }
|