- 给定一张\(n\)个点\(m\)条边的有向图，要求从\(1\)号点走到\(n\)号点，如果到达的时间超过\(t\)则需要交\(x\)元的罚款。
- 每条边有一个通过代价\(c_i\)，通过第\(i\)条边的时间为\(j(j\in[1,t])\)的概率为\(p_{i,j}\)。
- 求最小代价。
- \(n\le50,m\le100,t\le2\times10^4\)
暴力\(DP\)
至少这道题暴力还是比较好想的。
直接设\(f_{i,j}\)表示当前在\(i\)号点，时刻为\(j\)时走到\(n\)号点的最小代价。
暴力的转移就是从大到小枚举时刻\(j\)，枚举每一条边，再枚举通过的时间转移，得出转移式：
\[f_{a_i,j}=\min\{c_i+\sum_{k=1}^tp_{i,k}\times f_{b_i,j+k}\} \]特殊地，如果\(j> t\)，显然无论再走多久都已经迟到了，那么索性不管时间直接选择代价最短的路\(dis(i,n)+x\)，这部分可以事先\(Floyd\)预处理出来。
分治\(FFT\)
发现\(\sum_{k=1}^tp_{i,k}\times f_{b_i,j+k}\)只要把其中一个数组的下标翻转一下，就能变成卷积的形式。
方便起见，我们令\(g_{i,j}\)表示时刻为\(j\)时选第\(i\)条边的贡献，因为上面的转移都是针对一条边的两个端点进行的。
而\(f\)显然可以通过\(g\)来计算：
\[f_{x,j}=\min_{a_i=x}\{c_i+g_{i,j}\} \]发现这样还有一个大好事就是转移式中的\(\min\)被我们直接拎出来了，现在就变成了一个非常板子的卷积：
\[g_{i,j}=\sum_{k=1}^tp_{i,k}\times f_{b_i,j+k} \]要求这个就得考虑分治\(FFT\)。
以第二维为下标进行\(CDQ\)分治，每次先处理掉右区间的转移，然后考虑右区间对于左区间的贡献，即：
\[g_{i,j}=\sum_{k=mid+1}^rp_{i,k}\times f_{b_i,j+k} \]给它下标变个形，真正写成卷积的形式，即令\(a_k=p_{i,k+1},b_k=f_{b_i,r-k}\)，那么原式就变成了：
\[\begin{align} g_{i,j}&=\sum_{k=mid+1}^ra_{k-1}\times b_{r-(j+k)}\\ &=\sum_{x+y=r-j-1}a_x\times b_y\\ &=[x^{r-j-1}]A(x)*B(x) \end{align} \]代码：\(O(mtlog^2t)\)
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 50
#define M 100
#define LIM 20000
#define DB double
#define Gmin(x,y) (x>(y)&&(x=(y)))
using namespace std;
int n,m,lim,ex,a[M+5],b[M+5],c[M+5],dis[N+5][N+5];DB p[M+5][2*LIM+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
namespace Poly
{
int P,L,R[LIM<<3];const DB Pi=acos(-1);
struct node
{
DB x,y;I node(Con DB& a=0,Con DB& b=0):x(a),y(b){}
I node operator + (Con node& o) Con {return node(x+o.x,y+o.y);}
I node operator - (Con node& o) Con {return node(x-o.x,y-o.y);}
I node operator * (Con node& o) Con {return node(x*o.x-y*o.y,x*o.y+y*o.x);}
}A[LIM<<3],B[LIM<<3];
I void FFT(node* s,CI op)
{
RI i,j,k;node x,y,U,S;for(i=0;i^P;++i) i<R[i]&&(swap(s[i],s[R[i]]),0);
for(i=1;i^P;i<<=1) for(U=node(cos(Pi/i),op*sin(Pi/i)),j=0;j^P;j+=i<<1)
for(S=1,k=0;k^i;S=S*U,++k) s[j+k]=(x=s[j+k])+(y=S*s[i+j+k]),s[i+j+k]=x-y;
}
I void Mul(CI n,CI m)//多项式乘法
{
RI i;P=1,L=0;W(P<=n+m) P<<=1,++L;for(i=0;i^P;++i) R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
for(i=n+1;i^P;++i) A[i]=0;for(i=m+1;i^P;++i) B[i]=0;
for(FFT(A,1),FFT(B,1),i=0;i^P;++i) A[i]=A[i]*B[i];for(FFT(A,-1),i=0;i<=n+m;++i) A[i]=A[i].x/P;
}
DB f[N+5][2*LIM+5],g[M+5][LIM+5];I void CDQ(CI l,CI r)//分治FFT
{
RI i,j;if(l>lim) {for(i=1;i<=n;++i) for(j=l;j<=r;++j) f[i][j]=dis[i][n]+ex;return;}//对于j>lim的情况就是最短路+罚款
if(l==r) {for(i=1;i^n;++i) f[i][l]=1e9;for(i=1;i<=m;++i) a[i]^n&&Gmin(f[a[i]][l],c[i]+g[i][l]);return;}//边界
RI mid=l+r>>1;for(CDQ(mid+1,r),i=1;i<=m;++i) if(a[i]^n)//先做右区间，然后考虑右区间对左区间的贡献
{
for(j=0;j<=r-l-1;++j) A[j]=p[i][j+1];for(j=0;j<=r-mid-1;++j) B[j]=f[b[i]][r-j];//转化成卷积的形式
for(Mul(r-l-1,r-mid-1),j=l;j<=mid;++j) g[i][j]+=A[r-j-1].x;//卷积后统计答案
}CDQ(l,mid);//先做左区间
}
}
int main()
{
RI i,j,x;for(read(n,m,lim,ex),i=1;i<=n;++i) for(j=1;j<=n;++j) dis[i][j]=i^j?1e9:0;//初始化距离
for(i=1;i<=m;++i) for(read(a[i],b[i],c[i]),Gmin(dis[a[i]][b[i]],c[i]),j=1;j<=lim;++j) read(x),p[i][j]=x/1e5;//记录每条边信息
for(RI k=1;k<=n;++k) for(i=1;i<=n;++i) for(j=1;j<=n;++j) Gmin(dis[i][j],dis[i][k]+dis[k][j]);//Floyd跑最短路
return Poly::CDQ(0,2*lim),printf("%.12lf\n",Poly::f[1][0]),0;
}