题意: 给了一个图 从1号节点走到N号节点，然后，每个地方有买卖盐的差价，然后求 到达N的最大价值，一旦走到N这个点就不能再走了，或者走到不能再别的世界走1和N这两个点，然后接下来
用一个 四维的数组记录状态，因为时间是递增的 也就是说不会出现循环，我们每次选取最小的时间来做，这样可以避免很多不必要的状态去搜索，要转移到别的点的时候后 考虑这个状态买卖盐和什么都不做，的转移到别人那，
#include <iostream> #include <algorithm> #include <string.h> #include <vector> #include <queue> #include <cstdio> using namespace std; typedef long long LL; int G; struct point{ int un,loc,bl,ti; point(int cuniver=0,int cloc=0,int cblat=0,int ct=0) { un=cuniver; loc=cloc; bl=cblat; ti=ct; } bool operator <(const point &rhs)const{ return ti>rhs.ti; } }; int dp[6][105][6][205]; int H[105],nx[500],to[500],numofE,tim[500]; int dist[500]; int N,M,B,K,R,T; void init(int n) { numofE=0; memset(H,0,sizeof(H)); memset(dp,-1,sizeof(dp)); } int price[5][105]; void add(int a, int b, int t, int m) { numofE++; dist[numofE]=m; tim[numofE]=t; to[numofE]=b; nx[numofE]=H[a]; H[a]=numofE; } bool in[6][105][6][205]; priority_queue<point> Q; void jin(point per, point now,int S) { if(now.bl<=B&&S-price[per.un][per.loc]>dp[now.un][now.loc][now.bl][now.ti]) { dp[ now.un ][ now.loc ][ now.bl ][ now.ti ]=S-price[per.un][per.loc]; if(in[now.un][now.loc][now.bl][now.ti]==false) { in[now.un][now.loc][now.bl][now.ti]=true; Q.push(now); } } } void chu(point per, point now, int S) { if(now.bl>=0&&S+price[per.un][per.loc]>dp[now.un][now.loc][now.bl][now.ti]) { dp[ now.un ][ now.loc ][ now.bl ][ now.ti ]=S+price[per.un][per.loc]; if(in[now.un][now.loc][now.bl][now.ti]==false) { in[now.un][now.loc][now.bl][now.ti]=true; Q.push(now); } } } void bfs() { dp[0][1][0][0]=R; memset(in,false,sizeof(in)); Q.push(point(0,1,0,0)); in[0][1][0][0]=true; point pp,tmp; while(!Q.empty()){ tmp=Q.top();Q.pop(); int S=dp[tmp.un][tmp.loc][tmp.bl][tmp.ti]; if( tmp.ti>=T || tmp.loc==N ) continue; if( tmp.loc!=1 && tmp.loc!=N ) { int H=(tmp.un+1)%K; if( tmp.ti + 1 <= T) { pp.bl=tmp.bl; pp.loc=tmp.loc; pp.ti=tmp.ti+1;pp.un=H; if( S > dp[ pp.un ][ pp.loc ][ pp.bl ][ pp.ti ] ) { dp[pp.un][pp.loc][pp.bl][pp.ti]=S; if(in[pp.un][pp.loc][pp.bl][pp.ti]==false) { Q.push(pp); in[pp.un][pp.loc][pp.bl][pp.ti]=true; } } pp.bl=tmp.bl+1; jin(tmp,pp,S); pp.bl=tmp.bl-1; chu(tmp,pp,S); } } for(int i=H[tmp.loc]; i; i=nx[i]) { int tt=to[i]; if(tmp.un!=0&&(tt==1||tt==N))continue; pp.un=tmp.un;pp.loc=tt; pp.ti=tmp.ti+tim[i]; pp.bl=tmp.bl; int cost=S-dist[i]; if(pp.ti>T)continue; if(cost>dp[pp.un][pp.loc][pp.bl][pp.ti]) { dp[pp.un][pp.loc][pp.bl][pp.ti]=cost; if(in[pp.un][pp.loc][pp.bl][pp.ti]==false) { in[pp.un][pp.loc][pp.bl][pp.ti]=true; Q.push(pp); } } if(tmp.loc!=1&&tmp.loc!=N) { pp.bl=tmp.bl+1; jin(tmp,pp,cost); pp.bl=tmp.bl-1; chu(tmp,pp,cost); } } } } int main() { int cas; scanf("%d",&cas); for(int cc=1; cc<=cas; cc++) { G=0; scanf("%d%d%d%d%d%d",&N,&M,&B,&K,&R,&T); init(N); 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++) { int a,b,t,m; scanf("%d%d%d%d",&a,&b,&t,&m); add(a,b,t,m); } bfs(); int ans=-1; for(int i=0; i<=T; i++) for(int j=0; j<=B; j++) ans=max(ans,dp[0][N][j][i]); if(ans==-1){ printf("Case #%d: Forever Alone ",cc); }else{ printf("Case #%d: %d ",cc,ans); } } return 0; }