CF553E Kyoya and Train

本文主要是介绍CF553E Kyoya and Train，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定一张 n 个点 m 条边的无重边无自环的有向图，你要从 1 号点到 n 号点去。
如果你在 t 时刻之后到达n 号点，你要交 x 元的罚款。
每条边从 $a_i$ 到 $b_i$ ，走过它需要花费 $c_i$ 元，多次走过同一条边需要多次花费。
走过每条边所需的时间是随机的，对于 k∈[1,t]， $\dfrac{p_{i,k}}{10^5}$ 表示走过第 i 条边需要时间 k 的概率。因此如果多次走过同一条边，所需的时间也可能不同。
你希望花费尽可能少的钱（花费与罚款之和）到达 n 号点，因此每到达一个点，你可能会更改原有的计划。
求在最优决策下，你期望花费的钱数。
$\leq 50，m \leq 100，t \leq 2 \times 10^4，x,c_i \le 10^6 ,\sum_{k=1}^t p_{i,k} = 10^5$ ，答案精度误差 $\leq 10^{-6}$ 。

Solution

FFT优化spfa多状态转移

正着设初始状态并不对劲，正难则反。
算了我⑧说了看这里罢

还是很能体现概率期望的灵活性。

转移时其实只有后面的时间能够影响前面的时间，其实是一个分层转移。那么我们可以通过CDQ分治时间计算，时间复杂度为 $O(mtlog^2t)$

这里写的是sb做法，直接FFT转移SPFA，时间复杂度 $O (n m t l o g t)$
dijkstra的话因为无法有效比较两个状态的优劣（第二维时间太多）而没法写

Code

#include<bits/stdc++.h>
using namespace std;
struct edge{int y,z,nxt;
}e[110];
int head[60],cnt;
void add(int x,int y,int z){cnt++;e[cnt].y=y;e[cnt].z=z;e[cnt].nxt=head[x];head[x]=cnt;
}
long long d[60];
bool vis[60];
struct data{int x;long long s;bool operator <(const data &v)const{return s>v.s;}
};
priority_queue<data>q1;
const double pi=acos(-1.0);
int n,m,t,S,bit,limit=1,rev[200010];
struct cp{double x,y;cp(double xx=0,double yy=0){x=xx,y=yy;}
}a[200010],b[200010],c[200010];
double p[110][200010],dis[60][200010];
cp operator + (cp u,cp v){return cp(u.x+v.x,u.y+v.y);		
}
cp operator - (cp u,cp v){return cp(u.x-v.x,u.y-v.y);		
}
cp operator * (cp u,cp v){return cp(u.x*v.x-u.y*v.y,u.x*v.y+u.y*v.x);	
}
void dijkstra(){for(int i=1;i<n;i++) d[i]=1e15;q1.push((data){n,0});while(!q1.empty()){data x=q1.top();q1.pop(),vis[x.x]=0;for(int i=head[x.x];i;i=e[i].nxt){int y=e[i].y,z=e[i].z;if(d[y]>d[x.x]+z){d[y]=d[x.x]+z;if(!vis[y]){q1.push((data){y,d[y]});vis[y]=true;}}}}//for(int i=1;i<=n;i++)//cout<<i<<" "<<d[i]<<endl;
}
void FFT(cp *A,int type){for(int i=0;i<limit;i++)if(i<rev[i]) swap(A[i],A[rev[i]]);for(int mid=1;mid<limit;mid<<=1){cp wn(cos(pi/mid),type*sin(pi/mid));for(int r=mid<<1,j=0;j<limit;j+=r){cp w(1,0);for(int k=0;k<mid;k++,w=w*wn){cp x=A[j+k],y=w*A[j+mid+k];A[j+k]=x+y,A[j+mid+k]=x-y;}	}}if(type==-1)for(int i=0;i<limit;i++)A[i].x/=limit;
}
void mul(double *A,double *B){for(int i=0;i<=2*t;i++)a[i]=cp(A[i],0),b[i]=cp(B[i],0);//,cout<<a[i].x<<" "<<b[i].x<<endl;;for(int i=2*t+1;i<limit;i++)a[i]=b[i]=cp(0,0);FFT(a,1),FFT(b,1);for(int i=0;i<limit;i++)c[i]=a[i]*b[i]; FFT(c,-1);
}
queue<int>q2; 
void spfa(){for(int i=1;i<=n;i++){for(int j=0;j<=t;j++)dis[i][j]=1e15;for(int j=t+1;j<=2*t;j++)dis[i][j]=d[i]+S; }for(int j=0;j<=t;j++)dis[n][j]=0;q2.push(n);while(!q2.empty()){int x=q2.front();q2.pop(),vis[x]=0;for(int i=head[x];i;i=e[i].nxt){int y=e[i].y,z=e[i].z;mul(dis[x],p[i]);bool flag=false;for(int j=0;j<=t;j++)if(dis[y][j]>c[t+j+1].x+z){dis[y][j]=c[t+j+1].x+z;flag=true;}if(flag&&!vis[y]){q2.push(y);vis[y]=1;}}}
}
int main(){int x,y,z;scanf("%d%d%d%d",&n,&m,&t,&S);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(y,x,z);for(int j=1;j<=t;j++){scanf("%lf",&p[i][j]);p[i][j]/=100000;}reverse(p[i]+1,p[i]+t+1);}dijkstra();while(limit<=4*t)limit<<=1,bit++;for(int i=0;i<limit;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));spfa();//for(int i=0;i<=2*t;i++)printf("%.10lf",dis[1][0]);
}