題目鏈接：點擊查看

題目大意：有n個點，m條邊，一個人要在時間T內從1走到n，并在途中進行交易，獲得盡可能多的錢。這個人身上最多能帶B包鹽，每到一個地方都需要交納一定的錢數，并且經過一定的時間才能通過，每個地方的鹽價不同，在這個地方他可以對身上的鹽進行買/賣/不買也不賣這三種操作，要求無論任何時候身上的錢數都不能小于0。除此之外，還有K個平行世界，編號為0~K-1，這個人初始化在第0個世界，并且要求到達n點時也要在第0個世界，不同世界不同點的鹽價不同，但相應道路的花費相同，這個人可以花費1點時間單位到達第(K+1)%K個平行世界，在滿足所有條件的基礎上，求最后剩余錢數的最大值

另外需要注意的幾個細節：

在點1和點n不能對鹽進行買或賣的操作

在點1和點n不能穿越時空進入到平行世界

因為圖為有向圖，所以到達點n后不再擴展

目的地必須是第0個平行世界中的點n

題目分析：題意說的很清楚了，從起點開始向外用bfs一層一層的擴展就好了，只不過需要維護的狀態多一點，一般走迷宮的bfs維護的都是一個二維數組，兩個維度分別維護x坐標和y坐標，數組內部維護的是最優解，即從起點擴展到該點的答案，因為是bfs，所以每個點至多只能被走一次，所以可以將狀態數組和vis數組合為一體，即初始化時將狀態數組賦值為一個狀態無法轉移到的數值，這個題目中就是非正數即可，還有幾個細節需要注意一下，當擴展到終點時不要直接退出，等bfs跑完后才可能會出現最優解，還有就是尋找最優解時只需要遍歷一遍到達終點的時間這一維變量即可，因為我開的是dp[n][k][b][time]，滿足最優解，n和k肯定是終點，這個沒法變動，b一定是0的時候才能保證錢最多，不然身上的鹽都浪費掉了，只要枚舉time這個變量維護一下最大值即可

上代碼吧：注意寫一下注釋防止把自己寫暈

#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<string> using namespace std; typedef long long LL;const int inf=0x3f3f3f3f;int N,M,B,K,R,T;int p[10][110];//p[k][n]int dp[110][10][10][210];//dp[n][k][b][time] struct No {int n,k,b,time;No(int _n,int _k,int _b,int _time){n=_n;k=_k;b=_b;time=_time;}bool operator<(const No &a)const{return time>a.time;} };struct Node {int to,t,cost;Node(int TO=0,int T=0,int C=0){to=TO;t=T;cost=C;} };vector<Node>node[110];int bfs() {memset(dp,0,sizeof(dp));priority_queue<No>q;dp[1][0][0][0]=R;q.push(No(1,0,0,0));bool flag=false;while(!q.empty()){No tem=q.top();q.pop();int u=tem.n;int k=tem.k;int time=tem.time;int b=tem.b;if(time>T)break; if(u==N)//到了n點就不在迭代 continue;//不穿越 for(int i=0;i<node[u].size();i++){Node temp=node[u][i];int v=temp.to;if(time+temp.t>T)continue;int cost=dp[u][k][b][time]-temp.cost;if(cost<0)continue;if(v==N&&k!=0)continue;if(v==N)//到達終點標記一下，不要continue或breakflag=true;if(u!=1&&u!=N){//買if(b+1<=B&&dp[v][k][b+1][time+temp.t]<cost-p[k][u]) {if(!dp[v][k][b+1][time+temp.t])q.push(No(v,k,b+1,time+temp.t));dp[v][k][b+1][time+temp.t]=cost-p[k][u];}//賣if(b>0&&dp[v][k][b-1][time+temp.t]<cost+p[k][u]) {if(!dp[v][k][b-1][time+temp.t])q.push(No(v,k,b-1,time+temp.t));dp[v][k][b-1][time+temp.t]=cost+p[k][u];}}//不買不賣if(dp[v][k][b][time+temp.t]<cost){if(!dp[v][k][b][time+temp.t])q.push(No(v,k,b,time+temp.t));dp[v][k][b][time+temp.t]=cost; }}//穿越int k1=(k+1)%K;int cost=dp[u][k][b][time];if(time+1>T)continue;if(u!=1&&u!=N){//買if(b+1<=B&&dp[u][k1][b+1][time+1]<cost-p[k][u]) {if(!dp[u][k1][b+1][time+1])q.push(No(u,k1,b+1,time+1));dp[u][k1][b+1][time+1]=cost-p[k][u];}//賣if(b>0&&dp[u][k1][b-1][time+1]<cost+p[k][u]) {if(!dp[u][k1][b-1][time+1])q.push(No(u,k1,b-1,time+1));dp[u][k1][b-1][time+1]=cost+p[k][u];}}//不買不賣if(dp[u][k1][b][time+1]<cost){if(!dp[u][k1][b][time+1])q.push(No(u,k1,b,time+1));dp[u][k1][b][time+1]=cost; }}if(!flag)return -1;int ans=0;for(int i=0;i<=T;i++)ans=max(ans,dp[N][0][0][i]);return ans; }int main() {int w;cin>>w;int kase=0;while(w--){scanf("%d%d%d%d%d%d",&N,&M,&B,&K,&R,&T);//一定注意一個變量和一個%d對應，一開始少寫了一個。。提前進入自閉模式 for(int i=0;i<K;i++)for(int j=1;j<=N;j++)scanf("%d",&p[i][j]);for(int i=1;i<=N;i++)node[i].clear();while(M--){int a,b,t,m;scanf("%d%d%d%d",&a,&b,&t,&m);node[a].push_back(Node(b,t,m));}printf("Case #%d: ",++kase);int ans=bfs();if(ans==-1)printf("Forever Alone\n");elseprintf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 4784 Dinner Coming Soon(bfs+动态规划+优先队列)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。