网上找不到题解。。也不知道是不是对的，反正给的四个测试用例是通过了。
先找到所有可能的通路，然后从通路上的每个点往外走一步，当走到第一个不在这些通路上的点时，立即重启游戏。这样就能最小化现实时间了。
计算公式
Ans = sum{可行路径的概率* 走到终点的花费} + sum{走到重启点的概率 * (对应的花费+Ans)}
如果每个点都只有一条路能到达：
先用dfs找到所有可行路上的点，记录下走到这个点的概率和花费。终点的概率*花费就是上面公式里第一部分的值。
哪些点是重启点呢？
从所有可行路上的点出发再走一步，如果这个新的点不在可行路上，那它就是重启点，算出对应的概率和花费就好了。
现在就剩一个问题了。
同一个点可能会被好几条可行的路径经过，也可能会被不可行的路径经过，这样的话一个点既可以是可行的，又可以是重启点。所以不能用点来描述，应该用状态来描述。
到一个点后判断能不能继续往下走只跟两个因素有关，当前点的位置（也就是下标）和已经花费掉的游戏时间。用这两个因素就能唯一确定一个状态了。有的是可行的，有的是不可行的，也就是dfs中剪枝掉的。所以只要在dfs中记录所有可行状态，以及对应的概率就可以了。花费的时间就是第二个下标。
计算重启点就从所有可行状态再多走一步，如果能走到不可行状态，那这个不可行状态就是重启状态。
#include<bits/stdc++.h>
using namespace std;
int state[105][20005]; //状态可行性
double pro[105][20005]; //状态概率
struct edge{
int v,w,x;
edge(int v_,int w_, int x_){
v = v_; w = w_; x = x_;
}
edge(){}
};
struct u_ttl{ //记录点id和花费的游戏时间
int u,l;
u_ttl(int u_, int l_){
u = u_; l = l_;
}
u_ttl(){}
};
vector<u_ttl> temp; //记录dfs中当前走过的状态
vector<edge> g[105]; //图
int n,m,L;
int cnt[105],isend[105]; //从一个点出发的所有x之和，当前点是否是结束点
double ttvalue(0), ttcoe(0); //计算公式里的数值和，ans前的系数和
int u,v,w,x;
void dfs(int u, int ttL, double p){
pro[u][ttL] += p;
if(isend[u]){
if(ttL<=L){
ttvalue += p*double(ttL);
for(int i=0;i<temp.size();++i) state[temp[i].u][temp[i].l] = 1;
return;
}
}
if(ttL>=L) return;
for(int i=0;i<g[u].size();++i){
temp.push_back(u_ttl(g[u][i].v,g[u][i].w+ttL));
dfs(g[u][i].v,g[u][i].w+ttL,p*double(g[u][i].x)/double(cnt[u]));
temp.pop_back();
}
}
int main(){
// freopen("jump4.in","r",stdin);
scanf("%d%d%d",&n,&m,&L);
for(int i=0;i<m;++i){
scanf("%d%d%d%d",&u,&v,&w,&x);
cnt[u] += x;
g[u].push_back(edge(v,w,x));
}
for(int i=1;i<=n;++i){
if(cnt[i]==0) isend[i] = 1;
}
state[1][0] = 1;
dfs(1,0,1);
double tp;
for(int i=1;i<=n;++i){
for(int j=0;j<20005;++j){
if(state[i][j]==1){
for(int k=0;k<g[i].size();++k){
if(state[g[i][k].v][j+g[i][k].w]!=1){
tp = pro[i][j] * (double(g[i][k].x)/double(cnt[i]));
ttcoe += tp;
ttvalue += tp * double(j+g[i][k].w);
}
}
}
}
}
double ans = ttvalue/(1-ttcoe);
printf("%.10lf",ans);
return 0;
}
时间复杂度弄不清了，大佬随便看看吧。。