题目分析

设 $f(x)$表示从 $x$走到终点，使用最优决策的期望时间。

显然首先要拓扑排序后按照拓扑序逆序做，初始值 $f(D)=0$。

若无自环和重边。

假设我在处理点 $x$，它可以到点 $y_1,y_2,…,y_k$，有边权 $w_1,w_2,…,w_k$。若已经确定好了到哪个点的边权是谁，则直接选 $f(y)+w$最小的那个走即可，而这个最小值，一共有 $K^2$种。

将 $y$和 $w$都从小到大排序。

枚举这个最小值，假设取 $f(y_i)+w_j$是最小值，算出其他 $y$可以有多少种选 $w$的方案，使得这个权值不会小于我们枚举的最小值，设 $y_t$有 $cnt_t$种方案。由于 $f(y)$较小的 $y$可以取的 $w$一定更少更大，较大的 $y$不能抢较小的取走的 $w$，所以总方案数一共为：

$$\prod_{t \not=i} (cnt_t-(t-1))$$
这个值除以 $k!$就是 $f(y_i)+w_j$是最小值的概率。

分析复杂度，相当于把所有边分成了 $n$组，每组都是 $O(n^3)$的，所以总复杂度是 $O(n^3)$的。

显然这是过不了的。

可以将所有数对 $(y,w)$按照 $f(y)+w$从小到大排序，然后依次处理每一个数对。当我从一个数对改而处理下一个数对的时候，只需要修改两个数对的 $y$的 $cnt$值，复杂度降为 $O(n^2 \log n)$。

重边

有重边的话，就把重边到达的 $y$点复制几个。

自环

将若干个 $x$加入 $y$数组中。

不过 $f(x)$还未知啊？

那就二分答案，若最后算出来的结果比二分的答案大，就将答案变大。小，就将答案变小。

当然，也可以用迭代，更快。

这样复杂度就变成 $O(n^2 \log^2 n)$的了，虽然还是能过，不过你也可以精细地实现一下，每次将带 $x$的数对和不带 $x$的归并排序，就可以做到 $O(n^2 \log n)$的了。

代码

一题写一年系列

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef pair<int,int> PR;
typedef double db;
const db inf=1e7,eps=5e-8;
const int N=1005;
int n,m,st,ed,tot,js;
int h[N],ne[N],to[N],du[N],stk[N],seq[N];db w[N];
db f[N],ww[N*N];PR p1[N*N],p2[N*N],p3[N*N];int nxt[N],cnt[N];
vector<db> self_loop[N];

void add(int x,int y,db z) {to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void toposort() {
    int top=0;
    for(RI i=1;i<=n;++i) if(!du[i]) stk[++top]=i;
    while(top) {
        int x=stk[top];--top,seq[++js]=x;
        for(RI i=h[x];i;i=ne[i]) {
            --du[to[i]];
            if(!du[to[i]]) stk[++top]=to[i];
        }
    }
}

bool cmp(int x,int y) {return f[x]<f[y];}
bool cmpp(PR A,PR B)
    {return f[nxt[A.first]]+ww[A.second]<f[nxt[B.first]]+ww[B.second];}
void work(int x) {
    int loop_sz=self_loop[x].size(),pjs1=0,pjs2=0,kjs;js=0;
    for(RI i=h[x];i;i=ne[i]) ++js,ww[js]=w[i],nxt[js]=to[i];
    sort(nxt+1,nxt+1+js,cmp);
    for(RI i=0;i<loop_sz;++i) ww[++js]=self_loop[x][i],nxt[js]=x;
    sort(ww+1,ww+1+js);
    if(js==0) return;
    for(RI j=1;j<=js;++j)
        for(RI i=1;i<=js;++i)
            if(nxt[i]!=x) p1[++pjs1]=(PR){i,j};
            else p2[++pjs2]=(PR){i,j};
    sort(p1+1,p1+1+pjs1,cmpp);

    db l=0,r=2e6;
    while(l+eps<r) {
        db mid=(l+r)/2.0;f[x]=mid;
        for(RI i=1,j=1,k=1;k<=pjs1+pjs2;++k)
            if(j>pjs2||(i<=pjs1&&cmpp(p1[i],p2[j]))) p3[k]=p1[i++];
            else p3[k]=p2[j++];
        int pos=js-loop_sz+1;db nowans=1,kans=0;
        for(RI i=1;i<=js-loop_sz;++i) if(f[nxt[i]]>mid) {pos=i;break;}
        for(RI i=1;i<=js-loop_sz;++i) {
            if(i<pos) cnt[i]=js-(i-1),nowans=nowans*(db)cnt[i]/(db)i;
            else cnt[i]=js-(i+loop_sz-1),nowans=nowans*(db)cnt[i]/(db)(i+loop_sz);
        }
        for(RI i=1;i<=loop_sz;++i) {
            cnt[js-loop_sz+i]=js-(pos-1+i-1);
            nowans=nowans*(db)cnt[js-loop_sz+i]/(db)(pos-1+i);
        }
        for(RI i=1;i<=pjs1+pjs2;++i) {
            if(nowans<1e-9) break;
            int k1=p3[i].first,k2=p3[i].second;
            nowans/=(db)cnt[k1],kans+=(f[nxt[k1]]+ww[k2])*nowans;
            --cnt[k1],nowans*=(db)cnt[k1];
        }
        if(kans>mid) l=mid;
        else r=mid;
    }
    f[x]=(l+r)/2.0;
}
void DP() {
    for(RI i=1;i<=n;++i) f[i]=inf;
    int flag=0;
    for(RI i=n;i>=1;--i) {
        if(seq[i]==ed) {flag=1,f[ed]=0;continue;}
        else if(!flag) continue;
        work(seq[i]);
    }
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(RI i=1;i<=m;++i) {
        int x,y;db z;
        scanf("%d%d%lf",&x,&y,&z);
        if(x==y) self_loop[x].push_back(z);
        else add(x,y,z),++du[y];
    }
    toposort(),DP();
    if(f[st]>1e6) puts("-1");
    else printf("%.7f\n",f[st]);
    return 0;
}