hdu4784

题意: 给了一个图 从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=,int cloc=,int cblat=,int ct=)

  {

      un=cuniver;

      loc=cloc;

      bl=cblat;

      ti=ct;

  }

  bool operator <(const point &rhs)const{

    return ti>rhs.ti;

  }

};

int dp[][][][];

int H[],nx[],to[],numofE,tim[];

int dist[];

int N,M,B,K,R,T;

void init(int n)

{

    numofE=;

    memset(H,,sizeof(H));

    memset(dp,-,sizeof(dp));

}

int price[][];

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[][][][];

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>=&&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[][][][]=R;

   memset(in,false,sizeof(in));

   Q.push(point(,,,));

   in[][][][]=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!= && tmp.loc!=N )

        {

            int H=(tmp.un+)%K;

            if( tmp.ti +  <= T)

            {

                pp.bl=tmp.bl;  pp.loc=tmp.loc;

                pp.ti=tmp.ti+;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+;

                    jin(tmp,pp,S);

                    pp.bl=tmp.bl-;

                    chu(tmp,pp,S);

            }

        }

        for(int i=H[tmp.loc]; i; i=nx[i])

        {

            int tt=to[i];

            if(tmp.un!=&&(tt==||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!=&&tmp.loc!=N)

            {

                pp.bl=tmp.bl+;

                jin(tmp,pp,cost);

                pp.bl=tmp.bl-;

                chu(tmp,pp,cost);

            }

        }

    }

}

int main()

{

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; cc++)

    {

        G=;

        scanf("%d%d%d%d%d%d",&N,&M,&B,&K,&R,&T);

        init(N);

        for(int i=; i<K; i++)

        {

           for(int j=; j<=N; j++)

           scanf("%d",&price[i][j]);

        }

        for(int i=; 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=-;

        for(int i=; i<=T; i++)

            for(int j=; j<=B; j++)

         ans=max(ans,dp[][N][j][i]);

        if(ans==-){

          printf("Case #%d: Forever Alone\n",cc);

        }else{

          printf("Case #%d: %d\n",cc,ans);

        }

    }

    return ;

}