题解 CF553E 【Kyoya and Train】

这道题可以用普通FFT就过掉，没必要用分治FFT呀

我们一个naive的思路是设 f[i][j] 表示你最少要花多少钱才能在时刻 j 到达位置 i。但是这个边界条件没有定义——你咋知道 f[1][k](k>0) 要花多少钱呢？按理说应该是 \infty，但是好像又不太对劲……

所以说我们仔细一想会发现这个状态是不行滴（我一开始就在这种思路上纠结了一晚上然后成功崩溃看了题解）。正难则反，我们考虑反着来，即设 f[i][j] 表示当前是 j 时刻在位置 i，最少还要花多少钱才能到达位置 n。

我们设 DIS_i 表示位置 i 到位置 n 最少要花多少钱（不考虑通过时间），则显然这个可以通过一遍Dijkstra求出。则对于 f[i][j](j>t)，我们必有 f[i][j]=DIS_i+x（x 是罚款），因为反正已经超时了，那就走最划算的路吧。

则我们考虑对于一条有向边 (x,y,z)，则 x 可以从 y 转移过来。设当前边的概率数组是 prob，则有

其中 \leftarrow 表示可以被转移，且有 k\in[0,t]。

我们考虑翻转 prob 数组。则翻转后，转移式就变成了

发现后面是个卷积，两项的下标和恒为 t+k+1，于是

然后就可以直接FFT转移辣。

然后因为是在图上转移，而如果用Dijkstra转移的话 f[x] 之间又没有明确的大小关系，故考虑直接SPFA（当然SPFA已经死了，但就算它死了复杂度仍然没问题）。则复杂度为 O(nmt\log t)，没有卡常就排到了首页靠前的位置。

代码：

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const double eps=1e-10;
const int N=200100;
int n,m,t,pay,head[60],DIS[60];
struct edge{
    int to,next,val;
}edge[110];
void ae(int u,int v,int w,int p){
    edge[p].next=head[u],edge[p].to=v,edge[p].val=w,head[u]=p;
}
double prob[110][N],dis[60][N],now[N];
int rev[N],lim=1,LG;
struct cp{
    double x,y;
    cp(double X=0,double Y=0){
        x=X,y=Y;
    }
    friend cp operator +(const cp &u,const cp &v){
        return cp(u.x+v.x,u.y+v.y);
    }
    friend cp operator -(const cp &u,const cp &v){
        return cp(u.x-v.x,u.y-v.y);
    }
    friend cp operator *(const cp &u,const cp &v){
        return cp(u.x*v.x-u.y*v.y,u.x*v.y+u.y*v.x);
    }
}A[N],B[N];
void FFT(cp *a,int tp){
    for(int i=0;i<lim;i++)if(rev[i]>i)swap(a[rev[i]],a[i]);
    for(int md=1;md<lim;md<<=1){
        cp rt=cp(cos(pi/md),tp*sin(pi/md));
        for(int stp=md<<1,pos=0;pos<lim;pos+=stp){
            cp w=cp(1,0);
            for(int i=0;i<md;i++,w=w*rt){
                cp x=a[pos+i],y=a[pos+md+i]*w;
                a[pos+i]=x+y;
                a[pos+md+i]=x-y;
            }
        }
    }
    if(tp==-1)for(int i=0;i<lim;i++)a[i].x/=lim;
}
void mul(double *a,double *b,double *c){
    for(int i=0;i<lim;i++)A[i]=B[i]=cp(0,0);
    for(int i=0;i<(lim>>1);i++)A[i]=cp(a[i],0),B[i]=cp(b[i],0);
    FFT(A,1),FFT(B,1);
    for(int i=0;i<lim;i++)A[i]=A[i]*B[i];
    FFT(A,-1);
    for(int i=0;i<lim;i++)c[i]=A[i].x;
}
bool vis[60];
void Dijkstra(){
    priority_queue<pair<int,int> >q;
    for(int i=1;i<=n;i++)DIS[i]=0x3f3f3f3f;
    DIS[n]=0,q.push(make_pair(0,n));
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x])continue;vis[x]=true;
        for(int i=head[x],y;i!=-1;i=edge[i].next){
            y=edge[i].to;
            if(DIS[y]>DIS[x]+edge[i].val)DIS[y]=DIS[x]+edge[i].val,q.push(make_pair(-DIS[y],y));
        }
    } 
}
bool in[60];
void SPFA(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=t;j++)dis[i][j]=0x3f3f3f3f;
        for(int j=t+1;j<=2*t;j++)dis[i][j]=DIS[i]+pay;
    }
    for(int j=0;j<=t;j++)dis[n][j]=0;
    q.push(n),in[n]=true;
    while(!q.empty()){
        int x=q.front();q.pop(),in[x]=false;
        for(int i=head[x],y;i!=-1;i=edge[i].next){
            y=edge[i].to,mul(dis[x],prob[i],now);
            bool modi=false;
            for(int j=0;j<=t;j++)if(dis[y][j]>now[t+1+j]+edge[i].val)modi=true,dis[y][j]=now[t+1+j]+edge[i].val;
            if(modi&&!in[y])in[y]=true,q.push(edge[i].to);
        }
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&t,&pay),memset(head,-1,sizeof(head));
    for(int i=1,x,y,z;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z),ae(y,x,z,i);
        for(int j=1;j<=t;j++)scanf("%d",&x),prob[i][j]=1.0*x/100000;
        reverse(prob[i]+1,prob[i]+t+1);
    }
    while(lim<=(t<<2))lim<<=1,LG++;
    for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(LG-1));
    Dijkstra();
    SPFA();
    printf("%.10lf\n",dis[1][0]);
    return 0;
}