题目大意

链接：

给一张\(n\)个点，\(m\)条边的图，起点\(1\)终点\(n\)，如果不能在\(T\)的时间内到达则需支付\(X\)的代价。

走每条边都会支付一定代价，经过一条边\(i\)的时间有\(p_{i,j}\)的概率为\(j\)，最小化期望代价。

题目分析

暴力方法：期望DP

设\(f_{i,j}\)表示在第\(j\)时刻，从\(i\)点出发，到达终点的期望花费，

设边为\(e\)，边上两点为\(x,y\)，边集为\(E\)，则有

\[ f(x,t)=\min\limits_{e\in E}\{val_{e}+\sum_{i=1}^Tp_{e,i}\cdot f(y,t+i)\} \]

时间复杂度\(O(n\cdot T^2)\)。

或许你会觉得这样转移有问题，因为这不是一个DAG图，

但是，由于没有负权环，一个点不可能回到它的祖先，所以我们可以当做DAG来处理。

---

现在想想怎么优化这个DP。

我们设\(g_{e,t}\)表示\(\sum\limits_{i=1}^Tp_{e,i}\cdot f(y,t+i)\)，显然有

\[ f(x,t)=\min\{val_e+g(e,t)\} \]

我们可以利用分治。

如果要求出\(l\leq t\leq r\)的所有\(f(x,t)\)和\(g(e,t)\)，不妨设\(mid=l+r>>1\)，

先求出\(mid<t\leq r\)的\(f\)，并用这些\(f\)去更新\(l\leq t\leq mid\)的\(g\)，然后递归下去即可。

---

（方法co自的博客）

对于\(g(e,t)\)，我们可以考虑把它化为卷积的形式进行更新。

令\(mid=mid+1\)，对于\(g(e,mid-1)\)，我们有\(g(e,mid-1)+=\sum\limits_{i=0}^{r-mid+1}p_{e,i+1}\cdot f(e,mid+i)\)

我们把\(f\)数组反转，\(g(e,mid-1)+=\sum\limits_{i=0}^{r-mid+1}p_{e,i+1}\cdot f(e,r-i)\)。

在映射一下：\(g(e,mid-1)+=\sum\limits_{i=0}^{r-mid+1}p^{\prime}_{e,i}\cdot f^\prime(e,r-mid-i)\)。

即：\(g(e,mid-x)+=\sum\limits_{i=0}^{r-mid+1}p^{\prime}_{e,i}\cdot f^\prime(e,r-(mid-x)-i-1)\)

用\(ans(r-(mid-x)-1)\)来更新\(g(mid-x)\)，即用\(ans(r-t-1)\)来更新\(g(t)\)。

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 1<<30typedef long long LL;const int N=100005;using namespace std;inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}const double pi=acos(-1);struct Z{ double r,i; Z(double _r=0,double _i=0){r=_r,i=_i;} Z operator + (const Z &a)const{return Z(r+a.r,i+a.i);} Z operator - (const Z &a)const{return Z(r-a.r,i-a.i);} Z operator * (const Z &a)const{return Z(r*a.r-i*a.i,r*a.i+i*a.r);} Z operator / (const double &a)const{return Z(r/a,i/a);} Z operator /= (const double &a) {return *this=Z(r/a,i/a);}};void FFT(Z *a,int x,int K){ static int rev[N],lst; int n=1<
           
            >1]>>1)|((i&1)<
            
             =l;i--)g[j][i]+=a[r-i-1].r; }}void Binary(int l,int r){ if(l==r){ for(int i=1;i<=m;i++) f[s[i].x][l]=min(f[s[i].x][l],s[i].z+g[i][l]); return; } int mid=l+r>>1; Binary(mid+1,r); Cal(l,mid+1,r); Binary(l,mid);}int main(){ n=Getint(),m=Getint(),T=Getint(),X=Getint(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i^j)mp[i][j]=MAXN; for(int i=1;i<=m;i++){ int x=Getint(),y=Getint(),z=Getint(); s[i]=(node){x,y,z}; mp[x][y]=min(mp[x][y],1.0*z); for(int j=1;j<=T;j++)p[i][j]=(double)Getint()/100000; } Floyd(); for(int j=T+1;j<=2*T;j++)f[n][j]=X; for(int i=1;i