题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=4784

题意：一个人要到他男朋友家，他最初有R元以及T分钟的时间来赶到他男朋友家。有N个房子M条道路，每条道路有需要消耗的时间以及过路费，同时还要顺路做食盐生意，起初身上没有食盐，最多带B袋盐，每到达一个地方有三种操作可以选择：1.售出一袋食盐；2：购买一袋食盐；3：什么都不做。然后你以为结束了？不！它还存在平行宇宙，在一个城市可以选择穿越平行宇宙到达另一个宇宙的这个城市，不同宇宙的食盐价格不同但是过路费和道路需要的时间是相同的，而且由于他是穿越党，他不能在别的宇宙回到自己家或者男朋友家，求最后能否到达他男朋友家以及最多能有多少钱。

解法：BFS或者直接DP。我是直接DP的，考虑DP[t][i][j][k]代表当前时间为t,在第i个宇宙，背包容量为j,当前house为k最多有多少钱，然后按照题意去转移即可，也可以把这个过程用BFS来写，道理都一样。


#include <bits/stdc++.h>
using namespace std;
int N,M,B,K,R,T;
const int maxn = 110;
const int maxm = 210;
struct node{
    int time,val,to,next;
    node(){}
}E[maxm];
int dp[210][10][10][110];
int p[10][210];
int head[maxn],edgecnt;
void init(){
    edgecnt=0;
    memset(head,-1,sizeof(head));
}
void add(int u, int v, int time, int val){
    E[edgecnt].time = time;
    E[edgecnt].val = val;
    E[edgecnt].to = v;
    E[edgecnt].next = head[u];
    head[u] = edgecnt++;
}
void solve(int t, int k, int b, int u, int val){
    for(int i=head[u]; ~i; i=E[i].next){
        int v = E[i].to;
        int tt = t + E[i].time;
        int w = E[i].val;
        if(tt <= T && val >= w){
            dp[tt][k][b][v] = max(dp[tt][k][b][v], val-w);
        }
    }
    if(u!=1&&t+1<=T){
        dp[t+1][(k+1)%K][b][u] = max(dp[t+1][(k+1)%K][b][u], val);
    }
}
int main(){
    int T_T, ks = 0;
    scanf("%d", &T_T);
    while(T_T--){
        init();
        scanf("%d %d %d %d %d %d", &N,&M,&B,&K,&R,&T);
        memset(p, 0, sizeof(p));
        for(int i=0; i<K; i++)
            for(int j=1; j<=N; j++)
                scanf("%d", &p[i][j]);
        for(int i=1; i<=M; i++){
            int u,v,t,w;
            scanf("%d %d %d %d", &u,&v,&t,&w);
            add(u, v, t, w);
        }
        //dp
        memset(dp, -1, sizeof(dp));
        dp[0][0][0][1] = R;
        for(int i=0; i<=T; i++){
            for(int j=0; j<K; j++){
                for(int x=0; x<=B; x++){
                    for(int u=1; u<N; u++){
                        if(dp[i][j][x][u] == -1) continue;
                        solve(i,j,x,u,dp[i][j][x][u]);
                        if(u>1&&x>0) solve(i,j,x-1,u,dp[i][j][x][u]+p[j][u]);
                        if(u>1&&x<B) solve(i,j,x+1,u,dp[i][j][x][u]-p[j][u]);
                    }
                }
            }
        }
        int ans = -1;
        for(int i=0; i<=T; i++){
            ans = max(ans, dp[i][0][0][N]);
        }
        if(ans == -1){
            printf("Case #%d: Forever Alone\n", ++ks);
        }else{
            printf("Case #%d: %d\n", ++ks, ans);
        }
    }
    return 0;
}