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

 ```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 #include #include #include #include #include #include #include #include   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]; queueq; 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; }```