终态很好确定啊。。。

$f_{n,i}=[i\ge t]x$

$f_{i,j}(i\ne n)=\begin{cases}dist_{i,n}+x~~~~~&j\ge t\\\min\limits_{a_k=i}\{\sum\limits_{l=1}^tf_{b_k,j+l}p_{k,l}+c_k\}&j<t\end{cases}$

实际上这个期望是这么求的。

设 $EX$ 表示 $a_i$ 到 $n$ 的期望代价。

由于图是一个dag,$X$ 仍然不是一个基础事件。

$X$ 还可以分为随机进入到一个节点 $b_i$ 代价 $c_i$ ,然后加上 $b_i$ 到 $n$ 的期望代价。

此时 $\omega \in \Omega_{b_i},X(\omega)=(f_{b_i,j+l}+c_k)$

于是 $EX=\min\limits_{b_i}\{\sum\limits_{\omega\in\Omega_{b_i}}X(\omega)\Pr(\omega)\}$

由于 $\sum_{\omega\in\Omega_{b_i}}\Pr(\omega)=1$

所以 $c$ 可以提出来,转化出来就是上面的那个式子。

然后观察上面的式子,实际上他是一个可以卷积的式子,

设 $g_{i,j}$ 表示经过 $i$ 这条边,已经过了时间 $t$ 的期望代价 ,

则有 $f_{a_i,j}=\min\{f_{a_i,j},g_{i,j}=\sum\limits_{l=1}^tf_{i,j+l}p_{i,l}+c_i\}$

分治 $j$ 即可,先处理右区间。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n)) 
using namespace std;
const int MaxN=4e5+5,N=55,M=105,T=2e4+5;
const double pi=acos(-1),inf=1e10;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct cp
{
    double x,y;
    cp(double x=0.0,double y=0.0):x(x),y(y){}
    I cp operator +(const cp &a)const{return cp(x+a.x,y+a.y);}
    I cp operator -(const cp &a)const{return cp(x-a.x,y-a.y);}
    I cp operator *(const cp &a)const{return cp(x*a.x-y*a.y,y*a.x+x*a.y);}
    I cp operator +(const double &a)const{return cp(x+a,y+a);}
    I cp operator -(const double &a)const{return cp(x-a,y-a);}
    I cp operator /(const double &a)const{return cp(x/a,y/a);}
    I cp operator *(const double &a)const{return cp(x*a,y*a);}
}w[MaxN<<1];int tr[MaxN<<1],cnt;
I void init(int n){for(int i=1;i<n;i<<=1){w[i]=cp(1,0);for(int j=1;j<i;j++)w[i+j]=(((j&31)==1)?cp(cos(pi*j/i),sin(pi*j/i)):w[i+j-1]*w[i+1]);}}
I void rev(int n){if(cnt==n)return ;cnt=n;for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1|((i&1)?n>>1:0));}
void dft(cp *g,bool op,int n)
{
    rev(n);
    static cp f[MaxN<<1],t;
    for(int i=0;i<n;i++)f[i]=g[tr[i]];
    for(int p=2,l=1;p<=n;l=p,p<<=1)
        for(int i=0;i<n;i+=p)for(int j=0;j<l;j++)
            t=w[j|l]*f[i|j|l],f[i|j|l]=f[i|j]-t,f[i|j]=f[i|j]+t;
    if(op)for(int i=0;i<n;i++)g[i]=f[i]/n;
    else for(int i=0;i<n;i++)g[i]=f[i];
}
I void px(cp *f,cp *g,int n){for(int i=0;i<n;i++)f[i]=f[i]*g[i];}
cp _g1[MaxN<<1];
#define sav _g1
void times(cp *f,cp *g,int l1,int l2,int limit)
{
    int n=1,m=l1+l2-1;for(;n<m;n<<=1);
    for(int i=0;i<l2;i++)sav[i]=g[i];for(int i=l2;i<n;i++)sav[i]=cp(0,0);
    for(int i=l1;i<n;i++)f[i]=cp(0,0);
    dft(f,0,n);dft(sav,0,n);
    px(f,sav,n);reverse(f+1,f+n);dft(f,1,n);
    for(int i=limit;i<n;i++)f[i]=cp(0,0);
}
#undef sav
cp A[MaxN<<1],B[MaxN<<1];
double d[N][N],c[M],p[M][T<<1],f[N][T<<1],g[M][T];
int n,m,t,x,a[M],b[M];
void cdq(int l,int r)
{
    if(l==t)return ;
    if(l==r)
    {
        for(int i=1;i<n;i++)f[i][l]=inf;
        for(int i=1;i<=m;i++)
            if(a[i]!=n)f[a[i]][l]=min(f[a[i]][l],g[i][l]+c[i]);
        return ;
    }
    int mid=(l+r)>>1;
    cdq(mid+1,r);
    int l1=r-l-1,l2=r-mid-1;
    for(int i=1;i<=m;i++)
        if(a[i]!=n)
        {
            for(int j=0;j<=l1;j++)A[j]=cp(p[i][j+1],0);
            for(int j=0;j<=l2;j++)B[j]=cp(f[b[i]][r-j],0);
            times(A,B,l1+1,l2+1,l1+l2+1);
            for(int j=l;j<=mid;j++)g[i][j]+=A[r-j-1].x;
        }
    cdq(l,mid);
}
int main()
{
    qr(n),qr(m),qr(t),qr(x);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)d[i][j]=inf;
    for(int i=1,ww;i<=m;i++)
    {
        qr(a[i]),qr(b[i]),qr(ww),c[i]=d[a[i]][b[i]]=ww;
        for(int j=1;j<=t;j++)qr(ww),p[i][j]=ww/1e5;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)    
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    for(int i=0;i<2*t;i++)f[n][i]=i<=t?0:x;
    for(int i=1;i<n;i++)
        for(int j=t;j<2*t;j++)
            f[i][j]=d[i][n]+x;
    init(t<<2);
    cdq(0,2*t-1);
    printf("%.10lf\n",f[1][0]);
    return 0;
}