d8fa0cb0.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

namespace Solve
{
    template <typename Tp>
    inline void checkMax(Tp &x, const Tp &y)
    {
        if (x < y)
        {
            x = y;
        }
    }

    const int N = 100 + 5;
    const int M = 200 + 5;
    const int B = 4 + 5;
    const int K = 5 + 5;
    const int T = 200 + 5;

    int f[T][K][N][B]; // 时刻 T，平行宇宙 K，节点 N，盐 B 时手头的最大钱数。

    int head[N], E = 0;
    struct Edge
    {
        int to, next, time, money;
    } e[M];
    inline void addEdge(int u, int v, int time, int money)
    {
        e[++E] = (Edge){v, head[u], time, money};
        head[u] = E;
    }
    inline void clear(int n)
    {
        E = 0;
        memset(head + 1, 0, sizeof(int) * n);
    }

    int price[K][N];

    inline void solve()
    {
        int n, m, B, K, R, T;

        read(n), read(m), read(B), read(K), read(R), read(T);
        clear(n);

        for (int i = 0; i < K; ++i)
        {
            for (int k = 1; k <= n; ++k)
            {
                read(price[i][k]);
            }
        }
        for (int i = 1, u, v, time, price; i <= m; ++i)
        {
            read(u), read(v), read(time), read(price);
            addEdge(u, v, time, price);
        }

        for (int i = 0; i <= T; ++i)
        {
            memset(f[i], -1, sizeof(f[i]));
        }

        auto next = [&](const int &cur) {
            return cur == K - 1 ? 0 : cur + 1;
        };

        f[0][0][1][0] = R;

        for (int t = 0; t <= T; ++t) // 时间
        {
            for (int k = 0; k < K; ++k) // 平行宇宙
            {
                for (int u = 1; u <= n; ++u) // 节点
                {
                    for (int b = 0; b <= B; ++b) // 盐数
                    {
                        if (f[t][k][u][b] != -1 /* !(k > 0 && (u == 1 || u == n)) */ &&
                            !(k == 0 && u == n))
                        {
                            for (int i = head[u], v, dt; v = e[i].to, i; i = e[i].next)
                            {
                                dt = t + e[i].time;
                                if (!(k > 0 && (v == 1 || v == n)) &&
                                    dt <= T)
                                {
                                    if (price[k][v] != -1)
                                    {
                                        if (b + 1 <= B) // 买盐
                                        {
                                            checkMax(f[dt][k][v][b + 1], f[t][k][u][b] - e[i].money - price[k][v]);
                                        }
                                        if (b - 1 >= 0) // 卖盐
                                        {
                                            checkMax(f[dt][k][v][b - 1], f[t][k][u][b] - e[i].money + price[k][v]);
                                        }
                                    }
                                    checkMax(f[dt][k][v][b], f[t][k][u][b] - e[i].money); // 什么都不干
                                }
                            }
                            int dk = next(k), dt = t + 1;
                            if (!(dk > 0 && (u == 1 || u == n)) &&
                                dt <= T)
                            {
                                if (price[dk][u] != -1)
                                {
                                    if (b + 1 <= B) // 买盐
                                    {
                                        checkMax(f[dt][dk][u][b + 1], f[t][k][u][b] - price[dk][u]);
                                    }
                                    if (b - 1 >= 0) // 卖盐
                                    {
                                        checkMax(f[dt][dk][u][b - 1], f[t][k][u][b] + price[dk][u]);
                                    }
                                }
                                checkMax(f[dt][dk][u][b], f[t][k][u][b]); // 什么都不干
                            }
                        }
                    }
                }
            }
        }

        int ans = -1;

        for (int t = 0; t <= T; ++t)
        {
            for (int b = 0; b <= B; ++b)
            {
                checkMax(ans, f[t][0][n][b]);
            }
        }

        if (ans == -1)
        {
            puts("Forever Alone");
        }
        else
        {
            printf("%d\n", ans);
        }
    }
} // namespace Solve

int main()
{
    int T;
    read(T);

    for (int cas = 1; cas <= T; ++cas)
    {
        printf("Case #%d: ", cas);
        Solve::solve();
    }

    return 0;
}