The Ghost Blows Light
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1017 Accepted Submission(s): 303

Problem Description

My name is Hu Bayi, robing an ancient tomb in Tibet. The tomb consists of N rooms (numbered from 1 to N) which are connected by some roads (pass each road should cost some time). There is exactly one route between any two rooms, and each room contains some treasures. Now I am located at the 1st room and the exit is located at the Nth room.
Suddenly, alert occurred! The tomb will topple down in T minutes, and I should reach exit room in T minutes. Human beings die in pursuit of wealth, and birds die in pursuit of food! Although it is life-threatening time, I also want to get treasure out as much as possible. Now I wonder the maximum number of treasures I can take out in T minutes.

Input
There are multiple test cases.
The first line contains two integer N and T. (1 <= n <= 100, 0 <= T <= 500) Each of the next N - 1 lines contains three integers a, b, and t indicating there is a road between a and b which costs t minutes. (1<=a<=n, 1<=b<=n, a!=b, 0 <= t <= 100) The last line contains N integers, which Ai indicating the number of treasure in the ith room. (0 <= Ai <= 100) Output For each test case, output an integer indicating the maximum number of treasures I can take out in T minutes; if I cannot get out of the tomb, please output "Human beings die in pursuit of wealth, and birds die in pursuit of food!". Sample Input 5 10 1 2 2 2 3 2 2 5 3 3 4 3 1 2 3 4 5 Sample Output 11 Source 2012 ACM/ICPC Asia Regional Changchun Online DPDFSxdp[x][i]xiim2

?Download sourceCode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
 
using namespace std;
 
int n, m;
const int INF = 1 << 31 - 1;
 
struct node{
    int to;
    int next;
    int weight;
}e[201];
 
int w[210];
int lastshow[210];
int dp[210][510]; //dp[x][i]xm
bool inqueue[2010];
queue<int>q;
long long d[210];
int cnt = -1;
int used[210];
int path[210];
 
void insert(int a, int b, int w){
    e[++cnt].to = b;         //0
    e[cnt].weight = w;
    e[cnt].next = lastshow[a];
    lastshow[a] = cnt;
}
 
bool spfa(){
    q.push(1);
    int qq[2005];
    while(!q.empty()){
        int x = q.front();
        q.pop();
        inqueue[x] = false;
        int id = lastshow[x];
        while(id != -1){
            if(d[x] < INF && d[e[id].to] > e[id].weight + d[x]){
                d[e[id].to] = e[id].weight + d[x];
                path[e[id].to] = x;           //
                qq[e[id].to] = id;            //
                if(!inqueue[e[id].to]){
                    inqueue[e[id].to] = true;
                    q.push(e[id].to);
                }
            }
            id = e[id].next;
        }
    }
    int i;
    for(i = n; path[i] != -1; i = path[i]){   //path[i]!=-1i!=-10
        e[qq[i]].weight = 0;
    }
    return false;
}
 
void init(){
    int i;
    memset(used, 0, sizeof(used));
    memset(path, -1, sizeof(path));
    memset(dp, 0, sizeof(dp));
    memset(lastshow, -1, sizeof(lastshow));
    for(i = 1; i <= n; i ++){
        inqueue[i] = false;
    }
    for(i = 1; i <= n; ++ i)
        d[i]=INF;
    d[1]=0;
    cnt=-1;
    while(!q.empty()){
        q.pop();
    }
}
 
void dfs(int x){//dp
    used[x] = 1;
    for(int k = lastshow[x]; k!= -1; k = e[k].next){
        int y = e[k].to;
        if(used[y])
            continue;
        dfs(y); //
        int tmp = e[k].weight * 2;
        for(int i = m; i >= tmp; i --){
            for(int j = i - tmp; j >= 0; j --){
                dp[x][i] = max(dp[x][i], dp[x][j] + dp[y][i - tmp - j]);
            }
        }
    }
    for(int i = 0; i <= m; i ++){
        dp[x][i] += w[x];//x
    }
}
 
int main(){
    int i, j, k;
    while(~scanf("%d %d", &n, &m)){
        int a, b, c;
        init();
        for(i = 0; i < n - 1; i ++){
            scanf("%d %d %d", &a, &b, &c);
            insert(a, b, c);
            insert(b, a, c);
        }
        for(i = 1; i <= n; i ++){
            scanf("%d", &w[i]);
        }
        spfa();      //
        //cout << d[n] << endl;
        if(d[n] > m){
            printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
        }
        else{
            m -= d[n]; //
            dfs(1); 
            printf("%d\n", dp[1][m]);
        }
    }
    return 0;
}