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; }