Kyoya and Train

一个有\(n\)个节点\(m\)条边的有向图，每条边连接了\(a_i\)和\(b_i\)，花费为\(c_i\)。

每次经过某一条边就要花费该边的\(c_i\)。

第\(i\)条边耗时为\(j\)的概率为\(p_{i,j}\)。

现在你从\(1\)开始走到\(n\)，如果你在\(t\)单位时间内（包括\(t\)）到了\(n\)，不需要任何额外花费，否则你要额外花费\(x\)。

问你在最优策略下的期望花费最小为多少。（注意你每走一步都会根据当前情况制定最好的下一步）

\(n\leq 50 ,m \leq 100, t\leq 20000, x\leq 10^6\)

毛啸论文

看别人的代码，我学会了怎么用线性的空间预处理单位根。

\[\frac{2\pi}{2step}\times i=\frac{2\pi}{lim}\times \frac{lim}{2step}\times i
\]

而\(\frac{lim}{2step}\times i < \frac{lim}{2},i\in [0,step)\)，所以预处理\(\omega^{\frac{2\pi}{lim}}\)的次幂即可。

co double pi=acos(-1);

struct node {double x,y;};

il node operator+(co node&a,co node&b){

	return (node){a.x+b.x,a.y+b.y};

}

il node operator-(co node&a,co node&b){

	return (node){a.x-b.x,a.y-b.y};

}

il node operator*(co node&a,co node&b){

	return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};

}

co int N=55,M=105,T=20005,S=1<<15;

int n,m,t,punish;

int a[M],b[M],c[M],dis[N][N];

double dp[N][T],sum[M][T],p[M][T];

int rev[S];

node w[S],A[S],B[S];

void fourier_trans(node a[],int lim){

	for(int i=0;i<lim;++i)

		if(i<rev[i]) swap(a[i],a[rev[i]]);

	for(int step=1;step<lim;step<<=1){

		int quot=lim/(step<<1);

		for(int i=0;i<lim;i+=step<<1){

			int j=i+step;

			for(int k=0;k<step;++k){

				node t=w[quot*k]*a[j+k];

				a[j+k]=a[i+k]-t,a[i+k]=a[i+k]+t;

			}

		}

	}

}

void solve(int l,int r){

	if(l==r){

		for(int e=1;e<=m;++e)

			dp[a[e]][l]=min(dp[a[e]][l],sum[e][l]+c[e]);

		return;

	}

	int mid=(l+r)>>1;

	solve(mid+1,r);

	int len=int(ceil(log2(r-mid+r-l-1))),lim=1<<len;

	for(int i=0;i<lim;++i){

		rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);

		w[i]=(node){cos(i*2*pi/lim),sin(i*2*pi/lim)};

	}

	for(int e=1;e<=m;++e){

		for(int i=0;i<lim;++i)

			A[i]=B[i]=(node){0,0};

		for(int i=mid+1;i<=r;++i)

			A[i-mid-1]=(node){dp[b[e]][i],0};

		for(int i=1;i<=r-l;++i)

			B[r-l-i]=(node){p[e][i],0};

		fourier_trans(A,lim),fourier_trans(B,lim);

		for(int i=0;i<lim;++i){

			A[i]=A[i]*B[i];

			w[i].y=-w[i].y;

		}

		fourier_trans(A,lim);

		for(int i=0;i<lim;++i){

			A[i].x/=lim;

			w[i].y=-w[i].y;

		}

		for(int i=l;i<=mid;++i)

			sum[e][i]+=A[i-mid-1+r-l].x;

	}

	solve(l,mid);

}

int main(){

	scanf("%d%d%d%d",&n,&m,&t,&punish);

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			dis[i][j]=i==j?0:1e9;

	for(int i=1;i<=m;++i){

		scanf("%d%d%d",a+i,b+i,c+i);

		dis[a[i]][b[i]]=min(dis[a[i]][b[i]],c[i]);

		for(int j=1;j<=t;++j)

			scanf("%lf",p[i]+j),p[i][j]/=100000;

	}

	for(int k=1;k<=n;++k)

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j)

				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

	for(int i=0;i<N;++i)

		for(int j=0;j<T;++j)

			dp[i][j]=1e9;

	for(int i=1;i<=n;++i) dp[i][t+1]=punish+dis[i][n];

	for(int i=0;i<=t;++i) dp[n][i]=0;

	for(int e=1;e<=m;++e){

		double P=0;

		for(int i=1;i<=t;++i){

			P+=p[e][t+1-i];

			sum[e][i]=P*dp[b[e]][t+1];

		}

	}

	solve(0,t);

	printf("%lf\n",dp[1][0]);

	return 0;

}

巴特西

CF553E Kyoya and Train

Kyoya and Train

毛啸论文

最新文章

热门文章