随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 10010 , maxm = 30030;
int n , s , K;
int dp[maxn][15];
struct Edge {
    int v,w,next;   
}edge[maxm];
int E,head[maxn];
void init() {
    E=0;
    for(int i=1;i<=n;i++) head[i] = -1;   
    memset(dp,0,sizeof(dp));
}
void addedge(int u,int v,int w) {
    edge[E].v=v;edge[E].w=w;edge[E].next=head[u];head[u]=E++;
    edge[E].v=u;edge[E].w=w;edge[E].next=head[v];head[v]=E++;  
}
void dfs(int u,int pre) {
    for(int i=head[u];i!=-1;i=edge[i].next) {
        int v = edge[i].v , w = edge[i].w;
        if(v == pre) continue;
        dfs(v,u);
        for(int j=K;j>=0;j--) {
            dp[u][j] += dp[v][0] + 2 * edge[i].w;
            for(int k=1;k<=j;k++) {
                int tmp = dp[u][j-k] + dp[v][k] + k * edge[i].w;
                if(tmp < dp[u][j]) dp[u][j] = tmp;   
            }  
        }   
    }   
}
int main() {
    while(~scanf("%d%d%d",&n,&s,&K)) {
        init();
        int u,v,w;
        for(int i=1;i<n;i++) {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);   
        }
        dfs(s,-1);   
        printf("%d\n",dp[s][K]);
    }
    return 0;   
}