当时区域赛的一道题。题意大概是这样的，有一个1~N的图，然后你要从1－》N，其中每经过一条边需要消耗你的时间和金钱，每到一个地方可以选择什么都不做，或者买一包盐，卖一包盐，身上不能同时有超过B包盐，然后你还可以从当前所在的世界i转道(i+1)modK的世界，每次转换花费时间1，然后问你在T时间内到达n点的时候你最多能有多少钱。 那个时候不会做是因为不知道如何控制dp的方向，我记得那个时候我已经把状态写好了，转移也是知道的，就是不知道转移的方向，后来发现时间的那一维是降的，于是我们就可以建一个优先队列，把一开始的状态压进去，然后拓展新的状态，这样就可以做出来了，调了很久，因为我心里认为它是无向图。。。。。吸取教训呀要！
#pragma warning(disable:4996)#include#include #include #include #include #include #include #define maxn 150using namespace std;int n, m, B, K, R, T;int p[6][maxn];struct Edge{ int u, v, t, m; Edge(){} Edge(int ui, int vi, int ti, int mi) :u(ui), v(vi), t(ti), m(mi){}};vector G[maxn];int dp[6][maxn][5][250]; // dp[K][N][B][T] k维空间，第n个点，有b袋盐，剩余时间为T时的最多有多少钱bool vis[6][maxn][5][250];struct Node{ int k, n, b, t; Node(){} Node(int ki, int ni, int bi, int ti) :k(ki), n(ni), b(bi), t(ti){} bool operator < (const Node X) const{ return t < X.t; }};int main(){ int cas; cin >> cas; int ca = 0; while (cas--) { scanf("%d%d%d%d%d%d", &n, &m, &B, &K, &R, &T); for (int i = 0; i < K; i++){ for (int j = 1; j <= n; j++){ scanf("%d", &p[i][j]); } } for (int i = 0; i <= n; i++) G[i].clear(); int ui, vi, ti, mi; for (int i = 0; i < m; i++){ scanf("%d%d%d%d", &ui, &vi, &ti, &mi); G[ui].push_back(Edge(ui, vi, ti, mi)); } memset(dp, -1, sizeof(dp)); memset(vis, 0, sizeof(vis)); dp[0][1][0][T] = R; vis[0][1][0][T] = true; priority_queue que; que.push(Node(0, 1, 0, T)); while (!que.empty()){ Node nxt = que.top(); que.pop(); if (nxt.k == 0 && nxt.n == n) continue; int val = dp[nxt.k][nxt.n][nxt.b][nxt.t]; for (int i = 0; i < G[nxt.n].size(); i++){ Edge vv = G[nxt.n][i]; if (nxt.k != 0 && (vv.v == 1 || vv.v == n)) continue; if (nxt.t >= vv.t&&val >= vv.m){ dp[nxt.k][vv.v][nxt.b][nxt.t - vv.t] = max(dp[nxt.k][vv.v][nxt.b][nxt.t - vv.t], val - vv.m); if (!vis[nxt.k][vv.v][nxt.b][nxt.t - vv.t]){ que.push(Node(nxt.k, vv.v, nxt.b, nxt.t - vv.t)); vis[nxt.k][vv.v][nxt.b][nxt.t - vv.t] = true; } if (vv.v == 1 || vv.v == n) continue; if (nxt.b < B && (val - vv.m) >= p[nxt.k][vv.v]){ dp[nxt.k][vv.v][nxt.b + 1][nxt.t - vv.t] = max(dp[nxt.k][vv.v][nxt.b + 1][nxt.t - vv.t], val - vv.m - p[nxt.k][vv.v]); if (!vis[nxt.k][vv.v][nxt.b + 1][nxt.t - vv.t]){ que.push(Node(nxt.k, vv.v, nxt.b + 1, nxt.t - vv.t)); vis[nxt.k][vv.v][nxt.b + 1][nxt.t - vv.t] = true; } } if (nxt.b>0){ dp[nxt.k][vv.v][nxt.b - 1][nxt.t - vv.t] = max(dp[nxt.k][vv.v][nxt.b - 1][nxt.t - vv.t], val - vv.m + p[nxt.k][vv.v]); if (!vis[nxt.k][vv.v][nxt.b - 1][nxt.t - vv.t]){ que.push(Node(nxt.k, vv.v, nxt.b - 1, nxt.t - vv.t)); vis[nxt.k][vv.v][nxt.b - 1][nxt.t - vv.t] = true; } } } } if (nxt.t < 1) continue; if (nxt.n == 1 || nxt.n == n) continue; dp[(nxt.k + 1) % K][nxt.n][nxt.b][nxt.t - 1] = max(dp[(nxt.k + 1) % K][nxt.n][nxt.b][nxt.t - 1], val); if (!vis[(nxt.k + 1) % K][nxt.n][nxt.b][nxt.t - 1]){ que.push(Node((nxt.k + 1) % K, nxt.n, nxt.b, nxt.t - 1)); vis[(nxt.k + 1) % K][nxt.n][nxt.b][nxt.t - 1] = true; } if (nxt.b < B&&val >= p[(nxt.k + 1) % K][nxt.n]){ dp[(nxt.k + 1) % K][nxt.n][nxt.b + 1][nxt.t - 1] = max(dp[(nxt.k + 1) % K][nxt.n][nxt.b + 1][nxt.t - 1], val - p[(nxt.k + 1) % K][nxt.n]); if (!vis[(nxt.k + 1) % K][nxt.n][nxt.b + 1][nxt.t - 1]){ que.push(Node((nxt.k + 1) % K, nxt.n, nxt.b + 1, nxt.t - 1)); vis[(nxt.k + 1) % K][nxt.n][nxt.b + 1][nxt.t - 1] = true; } } if (nxt.b>0){ dp[(nxt.k + 1) % K][nxt.n][nxt.b - 1][nxt.t - 1] = max(dp[(nxt.k + 1) % K][nxt.n][nxt.b - 1][nxt.t - 1], val + p[(nxt.k + 1) % K][nxt.n]); if (!vis[(nxt.k + 1) % K][nxt.n][nxt.b - 1][nxt.t - 1]){ que.push(Node((nxt.k + 1) % K, nxt.n, nxt.b - 1, nxt.t - 1)); vis[(nxt.k + 1) % K][nxt.n][nxt.b - 1][nxt.t - 1] = true; } } } int ans = -1; for (int i = 0; i <= B; i++){ for (int j = 0; j <= T; j++){ ans = max(ans, dp[0][n][i][j]); } } printf("Case #%d: ", ++ca); if (ans == -1) puts("Forever Alone"); else printf("%d\n", ans); } return 0;}