hdu 4571 Travel in time(Floyd+記憶化)

題目鏈接：hdu 4571 Travel in time

題目大意：n個城市，m條路，總時間t，起始城市s，終點城市e，接下來給出各個城市的浏覽時間，各個城市浏覽後的滿意程度。然後是m條路的信息。要求一個浏覽順序，使得總的滿意程度最大，然後經過一個城市可以選擇不去浏覽，當前浏覽城市的滿意度一定要比前一個浏覽城市的滿意度高，並且最終要回到城市e

解題思路：因為經過一個城市可以不浏覽，所以先用Floyd處理一下各個城市之間的最短路徑，題目有個坑點就是說兩個城市間不至一條邊，要選最短的邊移動。

接著dfs+記憶化，dp[i][j][k]表示在第i個城市，前一個城市的滿意度為j，還剩下k的時間。

剪枝，當剩余時間不足以從i城市移動到e城市時，return -INF，這裡不可以是0，0表示的是可以到達。

#include 
#include 
#include 

using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;

int n, m, T, s, e;
int tc[N], vc[N], g[N][N];
int dp[N][N][3*N];

void Floyd () {
	for (int i = 0; i < n; i++)
		g[i][i] = 0;
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
				g[i][j] = min (g[i][j], g[i][k] + g[k][j]);
		}
	}
}

void init () {
	memset(dp, -1, sizeof(dp));
	memset(g, INF, sizeof(g));

	scanf("%d%d%d%d%d", &n, &m, &T, &s, &e);
	for (int i = 0; i < n; i++)
		scanf("%d", &tc[i]);
	for (int i = 0; i < n; i++)
		scanf("%d", &vc[i]);

	int a, b, v;
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &a, &b, &v);
		g[a][b] = g[b][a] = min(g[a][b], v);
	}

	Floyd ();
}

int dfs (int u, int val, int t) {
	if (g[u][e] > t) return -INF;

	if (dp[u][val][t] != -1) return dp[u][val][t];

	int& ans = dp[u][val][t];
	ans = 0;

	for (int i = 0; i < n; i++) {
		if (vc[i] <= val) continue;
		ans = max(ans, dfs(i, vc[i], t - tc[i] - g[u][i]) + vc[i]);
	}
	return ans;
}

int main () {
	int cas;
	scanf("%d", &cas);
	for (int i = 1; i <= cas; i++) {
		init ();
		printf("Case #%d:\n%d\n", i, dfs (s, 0, T));
	}
	return 0;
}