The Ghost Blows Light
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2549 Accepted Submission(s): 795
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
Recommend liuyiding | We have carefully selected several similar problems for you: 4272 4277 4274 4269 4275 题目大意：一颗树，从1点到n点，在t时间内走到，获得的最大价值 思路：先用spfa求最短路，如果>t,则到不了，t减去最短路，最短路上的边权改为0，如果走的不是最短路的话，来回为两倍的边权，即消耗为两倍的边权 ac代码
#include
#include
#include
#include
#include
#define max(a,b) (a>b?a:b) #define INF 0xfffffff using namespace std; int n,t; int a[110],head[110],vis[110],cnt,pre[110],dis[110],d[220],dp[110][10100]; struct s { int u,v,w,next; }edge[220]; void add(int u,int v,int w) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void spfa(int u) { int i; for(i=1;i<=n;i++) { dis[i]=INF; pre[i]=i; d[i]=0; } memset(vis,0,sizeof(vis)); vis[u]=1; dis[u]=0; queue
q; q.push(u); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; int w=edge[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; pre[v]=u; d[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } for(i=n;i!=1;i=pre[i]) { edge[d[i]].w=0; edge[d[i]^1].w=0; } } void dfs(int u,int pre) { int i,j,k; for(i=0;i<=t;i++) { dp[u][i]=a[u]; } for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v==pre) continue; dfs(v,u); int cost=edge[i].w*2; for(j=t;j>=cost;j--) { for(k=0;k+cost<=j;k++) { dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k-cost]); } } } } int main() { while(scanf(%d%d,&n,&t)!=EOF) { int i; memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); cnt=0; for(i=0;i
t) { printf(Human beings die in pursuit of wealth, and birds die in pursuit of food! ); continue; } t-=dis[n]; dfs(1,-1); printf(%d ,dp[1][t]); } }
?