题目链接：
思路：建图，对于同一个universe来说，就按题目给的条件相连，对于相邻的universe，连时间花费为1，费用为0的边，需要注意的是，对于起始点和终点只需在universe 0连边就可以了，对于相邻的universe则不需要建边。然后就是跑spfa了，其中dp[u][b][t]表示在顶点u，手中有b袋盐，花费时间为t的最大收益。
#include#include #include #include #include #include using namespace std;const int MAX_N = (233);const int inf = 0x3f3f3f3f;int N, M, B, K, R, T;struct Node { int v, time, cost; Node () {} Node (int _v, int _time, int _cost) : v(_v), time(_time), cost(_cost) {}};vector g[MAX_N * 5];int Kuniverse[7][MAX_N];void Build_Map(){ for (int i = 0; i <= N * K + 1; ++i) g[i].clear(); for (int i = 1; i <= M; ++i) { int a, b, t, m; scanf("%d %d %d %d", &a, &b, &t, &m); g[a - 1].push_back(Node(b - 1, t, m)); if (a != 1 && b != N) { for (int j = 1; j < K; ++j) { g[N * j + (a - 1)].push_back(Node( N * j + (b - 1), t, m)); } } } for (int i = 0; i < K; ++i) { for (int j = 1; j < N - 1; ++j) { g[i * N + j].push_back(Node(((i + 1) % K) * N + j, 1, 0)); } }}int dp[MAX_N * 5][7][MAX_N]; // 当前所在的位置，salt的数目，以及所花费的时间bool vis[MAX_N * 5][7][MAX_N]; struct State { int v, bag, t; State() {} State(int _v, int _bag, int _t) : v(_v), bag(_bag), t(_t) {} bool operator < (const State& s) const { return s.t < t; }};int spfa(int st, int ed){ for (int i = 0; i <= N * K + 1; ++i) { for (int j = 0; j <= B + 1; ++j) { for (int k = 0; k <= T + 1; ++k) dp[i][j][k] = -1, vis[i][j][k] = false; } } dp[0][0][0] = R; priority_queue que; //貌似不用优先队列要T... que.push(State(0, 0, 0)); while (!que.empty()) { State p = que.top(); que.pop(); vis[p.v][p.bag][p.t] = false; if (p.v == ed) continue; //这个条件没加wa，题目上说只要到达ed就立刻结束旅途 for (int i = 0; i < (int)g[p.v].size(); ++i) { Node node = g[p.v][i]; if (node.time + p.t <= T && dp[p.v][p.bag][p.t] - node.cost >= 0 && dp[p.v][p.bag][p.t] - node.cost > dp[node.v][p.bag][node.time + p.t]) { dp[node.v][p.bag][node.time + p.t] = dp[p.v][p.bag][p.t] - node.cost; if (!vis[node.v][p.bag][node.time + p.t]) { vis[node.v][p.bag][node.time + p.t] = true; que.push(State(node.v, p.bag, node.time + p.t)); } } if (Kuniverse[node.v / N][node.v % N] > 0 && p.bag > 0 && node.time + p.t <= T && dp[p.v][p.bag][p.t] - node.cost + Kuniverse[node.v / N][node.v % N] > dp[node.v][p.bag - 1][node.time + p.t]) { dp[node.v][p.bag - 1][node.time + p.t] = dp[p.v][p.bag][p.t] - node.cost + Kuniverse[node.v / N][node.v % N]; if (!vis[node.v][p.bag - 1][node.time + p.t]) { vis[node.v][p.bag - 1][node.time + p.t] = true; que.push(State(node.v, p.bag - 1, node.time + p.t)); } } if (Kuniverse[node.v / N][node.v % N] > 0 && p.bag + 1 <= B && node.time + p.t <= T && dp[p.v][p.bag][p.t] - node.cost - Kuniverse[node.v / N ][node.v % N] >= 0 && dp[p.v][p.bag][p.t] - node.cost - Kuniverse[node.v / N][node.v % N] > dp[node.v][p.bag + 1][node.time + p.t]) { dp[node.v][p.bag + 1][node.time + p.t] = dp[p.v][p.bag][p.t] - node.cost - Kuniverse[node.v / N][node.v % N]; if (!vis[node.v][p.bag + 1][node.time + p.t]) { vis[node.v][p.bag + 1][node.time + p.t] = true; que.push(State(node.v, p.bag + 1, node.time + p.t)); } } } } int ans = -1; for (int i = 0; i <= B; ++i) { for (int j = 0; j <= T; ++j) { if (dp[ed][i][j] > ans) ans = dp[ed][i][j]; } } return ans;} int main(){ int Cas, t = 1; scanf("%d", &Cas); 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 = 0; j < N; ++j) scanf("%d", &Kuniverse[i][j]); } Build_Map(); int ans = spfa(0, N - 1); printf("Case #%d: ", t++); if (ans == -1) { puts("Forever Alone"); } else printf("%d\n", ans); } return 0;}