LightOJ 1287 - 期望逃脫時間：狀態壓縮 DP + 記憶化搜索

問題建模

無向圖 n ≤ 15 個節點，從 0 出發。每步：

1. 在當前節點 u，找出所有「當選節點」EJ：移動到 v 後，仍能在不重複訪問節點的前提下遍歷所有安全節點（未被警察佔據）
2. 若無 EJ，遊戲結束
3. 否則：以等概率選擇「原地躲藏 5 分鐘」或「移動到某 EJ」（耗時邊權）

求警察抓住你的期望時間。

狀態定義

• dp[u][mask]：當前在節點 u，已訪問節點集合為 mask（含 u）時，後續期望時間
• ok[u][mask]：從 u 出發、已訪問 mask 的情況下，是否能遍歷完所有未訪問節點（即 u 是否為 EJ）

狀態轉移

先預處理 ok[][]（DFS + 記憶化）：

bool dfs(int u, int mask) {
    if ((mask | (1<

double DP(int u, int mask) {
    double &res = dp[u][mask];
    if (res != -1) return res;
    int cnt = 0;
    for (auto [v, w] : adj[u]) {
        if (mask & (1<

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 16;
vector> adj[MAXN];
double dp[MAXN][1<