简明题意：给出一个城市的道路网(是一棵树)，每条路有一定的权值，一个人在第k点，给出一些城市列表，问这个人游览完这些城市最小花费为多少
解法：一条最优的路线肯定是这样 

有且仅有一条路线是单向的。
下面定义状态:
dp[i][0]为游览完以i为根节点的子树（仅仅游览需要游览的城市，如果没有即为0）且最后回到i节点需要的最短长度 
dp[i][1]为不需要回到i节点的最短长度 
dp[i][0]=sum(dp[j][0]+val[i][j](如果dp[j][0]不为0或者j为需要访问的城市)),j为i的孩子节点 
dp[i][1]=dp[i][0]-max(dp[j][0]-dp[j][1]+val[i][j](如果dp[j][0]不为0或者j为需要访问的城市)) 
最后结果就是dp[start][1] 
程序如下 

 1# include <cstdio>
 2# include <cstring>
 3# include <vector>
 4//# include <algorithm>
 5using namespace std;
 6# define max(a,b) ((a)>(b)?(a):(b))
 7int dp[50001][2];
 8bool need[50001];
 9int g[50001],nxt[100005],val[100005],v[100005],c=0;
10inline void insert(int a,int b,int p)
11{
12   v[c]=b;
13   val[c]=p;
14   nxt[c]=g[a];
15   g[a]=c++;
16}
17void solve(int pos,int pre)
18{
19     int maxnum=0;
20     dp[pos][0]=dp[pos][1]=0;
21     for(int p=g[pos];p!=-1;p=nxt[p])
22       if(v[p]!=pre)
23       {
24          solve(v[p],pos);
25          maxnum=max(dp[v[p]][0]-dp[v[p]][1]+(dp[v[p]][0]||need[v[p]]?val[p]:0),maxnum);
26          dp[pos][0]+=dp[v[p]][0]+(dp[v[p]][0]||need[v[p]]?2*val[p]:0);
27       }
28     dp[pos][1]=dp[pos][0]-maxnum;
29}
30int main()
31{
32    int n,start,num;
33    scanf("%d%d",&n,&start);
34    memset(g,-1,sizeof(g));
35    memset(need,false,sizeof(need));
36    memset(dp,-1,sizeof(dp));
37    for(int i=1;i<n;i++)
38    {
39       int a,b,p;
40       scanf("%d%d%d",&a,&b,&p);
41       insert(a,b,p);
42       insert(b,a,p);
43    }
44    scanf("%d",&num);
45    while(num--)
46    {
47      int t;
48      scanf("%d",&t);
49      need[t]=true;
50    }
51    solve(start,-1);
52    printf("%d\n",dp[start][1]);
53   // system("pause");
54    return 0;
55}
56
57