题目链接：
题目大意：
有n个城市，编号为0~n-1，有m条有权无向边，有个小偷从编号为0的城市出发，他不会走已经走过的城市，
他有2种决策：
①停留在这个城市5分钟；
②如果城市i与现在所在城市相邻，且能在走到i后还能把剩下的城市遍历，则称i为EJ。在当前城市如果有cnt个EJ，那么他选择走向每个EJ的概率和停留在该城市的概率均为1/(cnt+1)
求小偷遍历完城市所需时间的期望值
(1 ≤ n ≤ 15)
图片说明
思路：我们预处理cnt[s][u]：访问的城市状态为s，如果去城市u能不能访问完所有剩余的城市。
然后记忆化状压DP就可以了。预处理cnt[s][u]也需要记忆化。

#include<bits/stdc++.h>
using namespace std;

vector<pair<int, int> > v[20];
int cnt[1<<16][15], n;
int vis[1<<16][15];
double f[1<<16][15];

int DFS(int u, int s){
    if(s==(1<<n)-1){
        return 1;
    }
    if(cnt[s][u]!=-1){
        return cnt[s][u];
    }
    cnt[s][u]=0;
    for(auto x: v[u]){
        int to=x.first;
        if(!(s&(1<<to))){
            cnt[s][u]|=DFS(to, s|(1<<to));
        }
    }
    return cnt[s][u];
}

double Dfs(int u, int s){
    if(vis[s][u]){
        return f[s][u];
    }
    int siz=1;
    for(auto x: v[u]){
        int to=x.first, w=x.second;
        if(!(s&(1<<to))&&cnt[s|(1<<to)][to]){
            siz++;
        }
    }
    if(siz>1){
        f[s][u]=5.0/(siz-1);
    }
    for(auto x: v[u]){
        int to=x.first, w=x.second;
        if(!(s&(1<<to))&&cnt[s|(1<<to)][to]){
            f[s][u]+=(Dfs(to, s|(1<<to))+w)/(siz-1);
        }
    }
    vis[s][u]=1;
    return f[s][u];
}

int main(){

    int t, cas=1; scanf("%d", &t);
    while(t--){
        memset(cnt, -1, sizeof(cnt));
        memset(f, 0, sizeof(f));
        memset(vis, 0, sizeof(vis));
        memset(v, 0, sizeof(v));
        int m, x, y, z;; scanf("%d%d", &n, &m);
        for(int i=1; i<=m; i++){
            scanf("%d%d%d", &x, &y, &z);
            v[x].push_back({y, z});
            v[y].push_back({x, z});
        }
        for(int s=0; s<(1<<n); s++){
            for(int i=0; i<n; i++){
                cnt[s][i]=DFS(i, s);
            }
        }
        printf("Case %d: %.8f\n", cas++, Dfs(0, 1));
    }

    return 0;
}