随笔档案

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define inf (1<<29)
const int maxn = 222 , maxm = 1111;
int dp[maxn][maxm] , n , m;
int w[maxn];
bool vis[maxn];
int dist[maxn], sta[maxn];
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;   
}
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++;   
}
int p[maxn],pre[maxn];
void spfa() {
    for(int i=1;i<=n;i++) dist[i]=inf,vis[i]=0;
    int top = 0;
    dist[1] = 0;
    sta[++top] = 1;
    while(top) {
        int u = sta[top --];
        vis[u] = 0;
        for(int i=head[u];i!=-1;i=edge[i].next) {
            int v = edge[i].v;
            if(dist[v] > dist[u] + edge[i].w) {
                dist[v] = dist[u] + edge[i].w;
                p[v] = u; pre[v] = i;   
                if(!vis[v]) {
                    vis[v] = 1;
                    sta[++top] = v;   
                }
            }   
        }   
    }   
    for(int i=n;i!=1;i=p[i])
        edge[pre[i]].w = 0;
    return;
}
void dfs(int u) {
    vis[u] = 1;
    for(int k=head[u];k!=-1;k=edge[k].next) {
        int v = edge[k].v;
        if(vis[v]) continue;
        dfs(v);
        int tmp = edge[k].w * 2;
        for(int i=m;i>=tmp;i--)
            for(int j=i-tmp;j>=0;j--)  
                dp[u][i]=max(dp[u][i],dp[u][j]+dp[v][i-tmp-j]);
    }   
    for(int i=0;i<=m;i++) dp[u][i] += w[u];
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        init();
        memset(dp,0,sizeof(dp));
        int u,v,ww;
        for(int i=1;i<n;i++) {
            scanf("%d%d%d",&u,&v,&ww);
            addedge(u,v,ww);   
        }   
        for(int i=1;i<=n;i++)
            scanf("%d",&w[i]);
        spfa();
        if(dist[n] > m)
        puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
        else {
            for(int i=1;i<=n;i++) vis[i] = 0;
            m -= dist[n];
            dfs(1);
            printf("%d\n",dp[1][m]);
        }
    }
    return 0;   
}