xtu summer individual 6 E - Find Metal Mineral

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define INF 0x3f3f3f3f
15 using namespace std;
16 struct arc {
17     int to,w;
18 };
19 vector<arc>g[10010];
20 int dp[10010][15],n,s,k;
21 void dfs(int u,int fa){
22     for(int i = 0; i < g[u].size(); i++){
23         int v = g[u][i].to;
24         if(v == fa) continue;
25         dfs(v,u);
26         for(int t = k; t >= 0; t--){
27             dp[u][t] += dp[v][0] + 2*g[u][i].w;
28             for(int j = 1; j <= t; j++)
29                 dp[u][t] = min(dp[u][t],dp[u][t-j]+dp[v][j]+j*g[u][i].w);
30         }
31     }
32 }
33 int main(){
34     while(~scanf("%d%d%d",&n,&s,&k)){
35         for(int i = 0; i <= n; i++)
36             g[i].clear();
37         for(int i = 1; i < n; i++){
38             int u,v,w;
39             scanf("%d %d %d",&u,&v,&w);
40             g[u].push_back((arc){v,w});
41             g[v].push_back((arc){u,w});
42         }
43         memset(dp,0,sizeof(dp));
44         dfs(s,-1);
45         printf("%d\n",dp[s][k]);
46     }
47     return 0;
48 }