【Codeforces 553E】Kyoya and Train
分治 FFT。
题目大意：
有 $n$ 个点，$m$ 条边的有向图，走过某一条边有一个价值 $w_i$。
对第 $i$ 条边，经过所需的时间为 $k$ 的概率为 $p_{i,k}$。
你要从 $1$ 走到 $n$，如果花费的时间大于 $t$，则需要额外花费 $x$ 的价值。
你可以任意时刻改变决策，求期望最小价值。
题解：
考虑倒着 dp。
令 $f[s][t]$ 表示从 $s$ 到 $n$，剩余时间为 $t$ 所要花的期望价值。
对于一条起点为 $x$，终点为 $s$ 的边 $d$，我们可以从 $s$ 的状态转移到 $x$。走这条边会有两种情况，一种是时间还有剩余，则接下来的期望就是那个点那个时间的 dp 值。一种是已经超时了，此时不管怎么走都要额外花费 $x$ 的价值，所以直接走 $s$ 到 $n$ 的价值最短路即可。
容易得到转移式：$f[x][t]=\min_d\{\sum_{a+b=t} f[s][a]\times p_{d,b}+\sum_{b>t}p_{d,b}\times(dist(y,n)+x)\}$
对于超时的情况，我们可以用后缀和优化。对于不超时的情况，转移是卷积的形式，可以考虑使用 FFT 加速。
由于图中可能存在环，我们并没有办法一次性直接转移。但是转移都是从剩余时间小的状态转移到剩余时间大的状态，所以我们考虑按剩余时间从小到大处理出每个点的 dp 值。
所以对时间进行 CDQ 分治，每次先计算左半部分的贡献，然后它们对右半部分的贡献可以使用 FFT 计算。
由于每个点的 dp 值是取其最小的一条边的 dp 值，所以我们分治 FFT 的时候把答案存在每条边上，到最底层时，再进行决策，得出每个点的 dp 值。
时间复杂度 $O(mt\log^2 t)$。
Code：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef double ld;
const ld pi=acos(-1);
const int N=32769;
struct cpx{
ld x,y;
inline cpx operator+(const cpx&r)const{return(cpx){x+r.x,y+r.y};}
inline cpx operator-(const cpx&r)const{return(cpx){x-r.x,y-r.y};}
inline cpx operator*(const cpx&r)const{return(cpx){x*r.x-y*r.y,x*r.y+y*r.x};}
}A[N],B[N],W[16][N];
ld f[55][20005],p[105][20005],suf[105][20005],F[105][20005];
int n,m,t,x,D[55][55],fr[105],to[105],w[105];
int rev[N],lim;
template<typename T>inline void chkmin(T&a,const T&b){a=(a>b)?b:a;}
inline void init(int n){
int l=-1;
for(lim=1;lim<n;lim<<=1)++l;
for(int i=1;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
}
void FFT(cpx*a){
for(int i=1;i<lim;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int i=1;i<lim;i<<=1){
const cpx*w=W[__builtin_ctz(i)];
for(int j=0;j<lim;j+=i<<1)
for(int k=0;k<i;++k){
const cpx x=a[j+k],y=a[j+k+i]*w[k];
a[j+k]=x+y,a[j+k+i]=x-y;
}
}
}
void Floyd(){
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)if(i!=k)
for(int j=1;j<=n;++j)if(i!=j&&j!=k)chkmin(D[i][j],D[i][k]+D[k][j]);
}
void solve(int l,int r){
if(l==r){
for(int i=1;i<n;++i)f[i][l]=1e9;
for(int i=1;i<=m;++i)chkmin(f[fr[i]][l],F[i][l]+w[i]+(D[to[i]][n]+::x)*suf[i][l+1]);
return;
}
const int mid=l+r>>1;
solve(l,mid);
for(int i=1;i<=m;++i){
const int y=to[i];
init(r-l+mid-l+2);
B[0]=(cpx){0};
for(int j=l;j<=mid;++j)A[j-l]=(cpx){f[y][j]};
for(int j=1;j<=r-l+1;++j)B[j]=(cpx){p[i][j]};
for(int j=mid-l+1;j<lim;++j)A[j]=(cpx){0};
for(int j=r-l+2;j<lim;++j)B[j]=(cpx){0};
FFT(A),FFT(B);
for(int j=0;j<lim;++j)A[j]=A[j]*B[j];
FFT(A);
reverse(A+1,A+lim);
for(int j=mid+1;j<=r;++j)F[i][j]+=A[j-l].x/lim;
}
solve(mid+1,r);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(int i=0;i<16;++i){
cpx*w=W[i];
*w=(cpx){1};
w[1]=(cpx){cos(pi/(1<<i)),sin(pi/(1<<i))};
for(int j=1;j<1<<i;++j)w[j]=w[1]*w[j-1];
}
cin>>n>>m>>t>>x;
memset(D,0x3f,sizeof D);
for(int i=1;i<=n;++i)D[i][i]=0;
for(int i=1;i<=m;++i){
cin>>fr[i]>>to[i]>>w[i];
D[fr[i]][to[i]]=w[i];
for(int j=1;j<=t;++j){int v;cin>>v;p[i][j]=v/1e5;}
for(int j=t;j;--j)suf[i][j]=suf[i][j+1]+p[i][j];
}
Floyd();
solve(0,t);
printf("%.9f",f[1][t]);
return 0;
}