ZOJ Monthly, June 2012 J : Escape Time II

問題概要

ノード数V(<10)の重み付き無向グラフが与えられる。また、各ノードには価値j[v]が与えられている。始点からスタートして様々なノードを訪ね価値を回収していく。時刻T(<10^7)までに終点にいなければならない。得られる価値を最大化する問題。

解法

まずWFしておく。その後はビットDP。
dp[v][bit] = {これまでに尋ねたノードがbitで今いるのがvであるような最小の時刻}
を全部計算して最後にdp[goal][bit] <= Tなるbitについて和をとればよい。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 10;
const int INF = 1<<29;

int graph[MAX_N][MAX_N];

int N, M, T, S, G;
int sum[1<<MAX_N];
int vs[MAX_N];
int dp[MAX_N][1<<MAX_N];

bool init() {
	if (scanf("%d%d%d", &N, &M, &T) == EOF) {
		return false;
	}
	scanf("%d%d", &S, &G);

	for (int i = 0; i < N; ++i) {
		scanf("%d", vs + i);
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			graph[i][j] = INF;
		}
	}

	for (int i = 0; i < M; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		graph[x][y] = min( graph[x][y], z );
		graph[y][x] = min( graph[y][x], z );
	}

	return true;
}

int solve() {
	for (int k = 0; k < N; ++k) {
		graph[k][k] = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}

	for (int bit = 0; bit < 1<<N; ++bit) {
		int tmp = 0;
		for (int i = 0; i < N; ++i) if((bit>>i)&1) {
			tmp += vs[i];
		}
		sum[bit] = tmp;
	}

	for (int i = 0; i < N; ++i) {
		fill(dp[i], dp[i] + (1<<N), INF);
	}

	dp[S][1<<S] = 0;
	for (int bit = 0; bit < 1<<N; ++bit) {
		for (int v = 0; v < N; ++v) {
			for (int u = 0; u < N; ++u) {
				const int nd = dp[v][bit] + graph[v][u];
				dp[u][bit | (1<<u)] = min( dp[u][bit | (1<<u)], nd );
			}
		}
	}

	int ans = 0;
	for (int bit = 0; bit < 1<<N; ++bit) {
		if (dp[G][bit] <= T) {
			ans = max(ans, sum[bit]);
		}
	}
	return ans;
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}

	return 0;
}