题意非常长非常变态。一个人要到他男朋友家，他最初有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;
}