1、http://acm.hdu.edu.cn/showproblem.php?pid=4276
2、题目大意：
一个墓中有n个房间，各个房间有连通的路，走每一条路都要花费一定的时间，并且每个房间都有一定量的财富，现在这个墓将在m分钟之后倒塌，从1号房间出发，出口在n号房间，求是否能安全逃出，如果能安全逃出去，输出可以获得的最大价值是多少？
dp[i][j]表示以i为根，花费J分钟可以获得的最大价值
我们首先从1号点到n号点求一个最短路径，我们最终要的答案，最短路径走一遍，在这个基础上在去别的分支取财富，所以别的分支都是去取完再回到最短路上，所以需要花费2倍的时间
dfs_time()求出最短路花费的时间，如果这个时间比要求的时间还要长，也就是说不管怎么走都走不出去
如果能出去，那么我们再用dfs()更新各个顶点为根的值，
dp[u][j]=max(dp[u][j],dp[u][j-k-2*w[i]]+dp[v][k]);
3、AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 105
int V[N*2],w[N*2],next[N*2],head[N*2];
int tot,tim,n,m,num[N];
int dp[N][505];
void add_edge(int a,int b,int c)
{V[tot]=b;w[tot]=c;next[tot]=head[a];head[a]=tot++;
}
int dfs_time(int u,int fa)
{if(u==n)return 1;for(int i=head[u];i!=-1;i=next[i]){int v=V[i];if(v!=fa){if(dfs_time(v,u)){tim+=w[i];w[i]=0;return 1;}}}return 0;
}
void dfs(int u,int fa)
{for(int i=0;i<=m;i++)dp[u][i]=num[u];for(int i=head[u];i!=-1;i=next[i]){int v=V[i];if(v!=fa){dfs(v,u);for(int j=m;j>=0;j--){for(int k=0;k<=j-w[i]*2;k++){dp[u][j]=max(dp[u][j],dp[u][j-k-2*w[i]]+dp[v][k]);}}}}
}
int main()
{int a,b,c;while(scanf("%d%d",&n,&m)!=EOF){tot=0;memset(head,-1,sizeof(head));for(int i=1;i<n;i++){scanf("%d%d%d",&a,&b,&c);add_edge(a,b,c);add_edge(b,a,c);}for(int i=1;i<=n;i++){scanf("%d",&num[i]);}tim=0;dfs_time(1,-1);if(tim>m)printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");else{m-=tim;dfs(1,-1);printf("%d\n",dp[1][m]);}}return 0;
}