poj 1849 Two

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<vector>
 6 #include<queue>
 7 using namespace std;
 8 
 9 vector<int>Q[100002];
10 vector<int>val[100002];
11 int num[100002];
12 bool use[100002];
13 int dp[100002][3];
14 
15 void add(int x,int y,int c)
16 {
17     Q[x].push_back(y);
18     val[x].push_back(c);
19     num[x]++;
20 }
21 int min(int x,int y)
22 {
23     return x>y ? y:x;
24 }
25 void dfs(int k)
26 {
27     int i,j,s,t,cur;
28     use[k]=true;
29     for(i=0;i<num[k];i++)
30     {
31         t=Q[k][i];
32         if(use[t]==true)continue;
33         dfs(t);
34         for(j=2;j>=0;j--)
35         {
36             dp[k][j]=dp[k][j]+2*val[k][i]+dp[t][0];
37             for(s=1;s<=j;s++)
38             {
39                 dp[k][j]=min(dp[k][j],dp[k][j-s]+dp[t][s]+s*val[k][i]);
40             }
41         }
42     }
43 }
44 int main()
45 {
46     int n,s,i;
47     int x,y,c;
48     while(scanf("%d%d",&n,&s)>0)
49     {
50         for(i=0;i<=n;i++)
51         {
52             Q[i].clear();
53             val[i].clear();
54             num[i]=0;
55             use[i]=false;
56         }
57         memset(dp,0,sizeof(dp));
58         for(i=1;i<n;i++)
59         {
60             scanf("%d%d%d",&x,&y,&c);
61             add(x,y,c);
62             add(y,x,c);
63         }
64         dfs(s);
65         printf("%d\n",dp[s][2]);
66     }
67     return 0;
68 }