首页 > 代码库 > HDU--4784 Dinner Coming Soon DP+BFS
HDU--4784 Dinner Coming Soon DP+BFS
题意非常长非常变态。一个人要到他男朋友家,他最初有R元以及T分钟的时间来赶到他男朋友家。有N个房子M条道路,每条道路有须要消耗的时间以及过路费,同一时候还要顺路做食盐生意,起初身上没有食盐,最多带B袋盐,每到达一个地方有三种操作能够选择:1.售出一袋食盐;2:购买一袋食盐;3:什么都不做。然后你以为结束了?不!它还存在平行宇宙,在一个城市能够选择穿越平行宇宙到达还有一个宇宙的这个城市,不同宇宙的食盐价格不同可是过路费和道路须要的时间是同样的,并且因为他是穿越党,他不能在别的宇宙回到自己家或者男朋友家,求最后是否能到达他男朋友家以及最多能有多少钱。
BFS+DP,由于时间是不可逆的,所以每次依照时间的先后来处理状态,因此须要用优先队列来处理。
#include <iostream> #include <cstdio> #include <cmath> #include <queue> #include <algorithm> #include <cstdlib> #include <vector> #include <iomanip> #include <set> using namespace std; typedef long long ll; const int maxn=111; const int maxm=222; struct Edge//邻接表 { int v; int tim;//时间花费 int cost;//金钱花费 int next; }; struct Node { int u,times,k,b; bool operator < (const Node &a) const { return times>a.times; } }; Edge edges[maxm<<1]; int head[maxn]; int num=-1;; int n,m,B,K,R,T; int dp[maxn][210][7][7]; int inqueue[maxn][210][7][7]; int price[7][maxn]; void addEdge(int u,int v,int tim,int cost) { num++; edges[num].v=v; edges[num].tim=tim; edges[num].cost=cost; edges[num].next=head[u]; head[u]=num; } int bfs() { int flag=0; memset(dp,0,sizeof(dp)); memset(inqueue,0,sizeof(inqueue)); dp[1][0][0][0]=R;//初始金钱 Node node,tmp; priority_queue<Node>q;//优先队列,按时间处理 node.u=1;//起始状态 node.times=0; node.k=0; node.b=0; inqueue[1][0][0][0]=1; q.push(node); while(!q.empty()) { node=q.top(); q.pop(); if(node.times>T)//当队里的元素的时间都大于T就无需处理了 { break; } int u=node.u; if(u==n) { //cout<<node.times<<endl; continue; } for(int i=head[u];i!=-1;i=edges[i].next)//走到下一个城市 { int v=edges[i].v; int cost,tim; cost=dp[u][node.times][node.k][node.b]-edges[i].cost;//剩下的金钱 tim=node.times+edges[i].tim;//时间 if(tim>T||cost<0)//剪枝 { continue; } if(v==n&&node.k!=0)//仅仅能在0宇宙到达第N个城市 { continue; } if(v==n)//成功到达 { flag=1; } tmp.u=v; tmp.times=tim; tmp.k=node.k; if(u!=1&&u!=n) { if(node.b+1<=B&&cost-price[node.k][u]>dp[v][tim][node.k][node.b+1])//买一袋盐 { dp[v][tim][node.k][node.b+1]=cost-price[node.k][u]; tmp.b=node.b+1; if(!inqueue[tmp.u][tmp.times][tmp.k][tmp.b]) { q.push(tmp); inqueue[tmp.u][tmp.times][tmp.k][tmp.b]=1; } } if(node.b>0&&cost+price[node.k][u]>dp[v][tim][node.k][node.b-1])//卖一袋盐 { dp[v][tim][node.k][node.b-1]=cost+price[node.k][u]; tmp.b=node.b-1; if(!inqueue[tmp.u][tmp.times][tmp.k][tmp.b]) { q.push(tmp); inqueue[tmp.u][tmp.times][tmp.k][tmp.b]=1; } } } if(cost>dp[v][tim][node.k][node.b])//不买盐 { dp[v][tim][node.k][node.b]=cost; tmp.b=node.b; if(!inqueue[tmp.u][tmp.times][tmp.k][tmp.b]) { q.push(tmp); inqueue[tmp.u][tmp.times][tmp.k][tmp.b]=1; } } } if(u!=1&&u!=n)//穿越到下一个宇宙的这个城市 { int cost=dp[u][node.times][node.k][node.b];//金钱不变 tmp.u=u; tmp.k=(node.k+1)%K; tmp.times=node.times+1;//看广告时间+1 if(tmp.times>T) { continue; } if(node.b+1<=B&&cost-price[node.k][u]>dp[u][tmp.times][tmp.k][node.b+1])//在这个宇宙的这个城市买盐 { dp[u][tmp.times][tmp.k][node.b+1]=cost-price[node.k][u]; tmp.b=node.b+1; if(!inqueue[tmp.u][tmp.times][tmp.k][tmp.b]) { q.push(tmp); inqueue[tmp.u][tmp.times][tmp.k][tmp.b]=1; } } if(node.b>0&&cost+price[node.k][u]>dp[u][tmp.times][tmp.k][node.b-1])//卖一袋盐 { dp[u][tmp.times][tmp.k][node.b-1]=cost+price[node.k][u]; tmp.b=node.b-1; if(!inqueue[tmp.u][tmp.times][tmp.k][tmp.b]) { q.push(tmp); inqueue[tmp.u][tmp.times][tmp.k][tmp.b]=1; } } tmp.b=node.b; if(cost>dp[u][tmp.times][tmp.k][tmp.b])//不做操作 { dp[u][tmp.times][tmp.k][tmp.b]=cost; if(!inqueue[tmp.u][tmp.times][tmp.k][tmp.b]) { q.push(tmp); inqueue[tmp.u][tmp.times][tmp.k][tmp.b]=1; } } } } if(!flag) { return -1;//不能到达 } int ans=0; for(int i=0;i<=T;i++) { for(int j=0;j<=B;j++) { ans=max(ans,dp[n][i][0][j]);//能够到达,在能够到的的情况中选取钱最多的 } } return ans; } int main() { int t; int s=1; int u,v,tim,cost; scanf("%d",&t); while(t--) { scanf("%d%d%d%d%d%d",&n,&m,&B,&K,&R,&T);//城市数目,道路数目,食盐上限,宇宙个数,初始金钱,时间上限 memset(head,-1,sizeof(head)); num=-1; for(int i=0;i<K;i++) { for(int j=1;j<=n;j++) { scanf("%d",&price[i][j]);//食盐在每一个宇宙每一个城市的价格 } } for(int i=0;i<m;i++) { scanf("%d%d%d%d",&u,&v,&tim,&cost);//每条路的起点,终点,时间,花费 addEdge(u,v,tim,cost); } int ans; ans=bfs(); printf("Case #%d: ",s++); if(ans!=-1) { printf("%d\n",ans); } else { printf("Forever Alone\n"); } } return 0; }
HDU--4784 Dinner Coming Soon DP+BFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。