(概率dp)

---

题面长长的，看了半天也没看懂题意

不清楚的地方，如何判断一个点是否是EJ

按照我的理解 在一个EJ点处，要么原地停留五分钟接着走，要么直接走，但是这样样例都对不上

mmp，原来是说，在原地停留五分钟后再继续这两种选择

而且题目问的是 求被警察抓的期望时间，实际上却是求遍历完整张图的期望时间，也就是说总是会走是EJ的点

对于每个点来说从该点出发的期望时间\(dp[i] = \frac{dp[i]+5}{cnt+1} + \frac{\sum(dp[j]+w[i][j])}{cnt+1} 其中j是所有下一个可达的EJ点，cnt表示可达的EJ点的个数\)

化简一下 $ dp[i] = \frac{5 + \sum(dp[j]+w[i][j])}{cnt}$

由于走的点不能重复，自然就是一个状压dp了，题目的点数n自然也就是\(n<=15\)的

dp[u][s] 表示从u出发 已经遍历图的结点状态为s 遍历完整张图的期望时间

can[u][s] 表示从u出发 已经遍历图的结点状态为s 能否遍历完整张图

然后同时记忆化搜索就好了

#include
    
     #define LL long longusing namespace std;const int N = 15;double dp[N][1<
     
      < n;i++){        if(g[u][i] && i != u && !((1<
      
       >T;    while(T--){        scanf("%d%d",&n,&m);        memset(g,0,sizeof(g));        for(int i = 0;i < m;i++){            int u, v, w;            scanf("%d%d%d",&u,&v,&w);            g[u][v] = g[v][u] = w;        }        printf("Case %d: ",cas++);    memset(can,-1,sizeof(can));    dfs(0,1);    printf("%.12f\n",dp[0][1]);}return 0;
      
     
    

}