题解 CF553E 【Kyoya and Train】

2020-08-16 17:37:03


这道题可以用普通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$,则有

$$f[x][k]\leftarrow z+\sum\limits_{j=1}^tprob_j\times f[y][j+k]$$

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

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

$$f[x][k]\leftarrow z+\sum\limits_{j=1}^tprob_{t-j+1}\times f[y][j+k]$$

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

$$f[x][k]\leftarrow z+(prob\times f[y])_{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;
}