【BZOJ 5047 空间传送装置】

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 282 Solved: 121
[Submit][Status][Discuss]

Description

太空中一共有n座星球，它们之间可以通过空间传送装置进行转移。空间传送装置分为m种，第i种装置可以用4个参

数a_i,b_i,c_i,d_i来描述。因为时空抖动的问题，在非整数时刻禁止使用空间传送装置。如果在整数s时刻使用装

置，那么需要花费((a_i*s+b_i) mod c_i)+d_i单位时间才能完成传送。现在是s时刻，小Q位于1号星球，请写一个

程序计算从1号星球到每个星球最少需要的时间。

Input

第一行包含4个正整数n,m,s,e(2<=n<=100000,1<=m<=50,1<=s<=2000,1<=e<=200000)

分别表示星球的个数、空间传送装置的种类数、当前的时间以及空间传送装置的个数。

接下来m行，每行4个正整数a_i,b_i,c_i,d_i(1<=a_i,b_i,c_i,d_i<=2000)，依次描述每种装置的参数。

接下来e行，每行3个正整数u_i,v_i,w_i(1<=u_i,v_i<=n,u_i!=v_i,1<=w_i<=m)

表示从星球u_i可以使用第w_i种装置单向传送到星球v_i。

Output

输出n-1行，每行一个整数，第i行表示从1到i+1的最少所需时间，若无解输出-1。

Sample Input

3 2 1 3
1 1 5 1
2 2 7 1
1 2 1
2 3 2
3 1 1

Sample Output

3
6
HINT
1到3：在时刻1使用第一种装置从1传送到2，花费时间3，再等待2单位时间，于时刻6使用第二种装置到达3，花费时间1。

题解：

①首先要发现问题具有周期性(产生原因：取模操作)

②由于设备数很小,所以可以记录取模的状态: D[i][j]表示第i个机器在时间%c[i]为j的情况下从一个点走到另一个点所需要花费的时间(时间=等候时间+行走时间)

③上述数组维护前后缀最小值,预处理得出

④最后进行一遍最短路就可以了

⑤贪心成立的依据:时间尽量小不会有坏处

#include<queue>

#include<stdio.h>

#include<algorithm>

#define go(i,a,b) for(int i=a;i<=b;i++)

#define ro(i,a,b) for(int i=a;i>=b;i--)

#define fo(i,a,x) for(int i=a[x],v=e[i].v;i;i=e[i].next,v=e[i].v)

using namespace std;const int N=100003;

int n,m,s,t;

int a[N],b[N],c[N],d[N];

int head[N],k=1,U,V,W;

int val[N],lef[N],rig[N],D[60][2007];

queue<int>q;bool inq[N];int dis[N];

struct E{int v,next,w;}e[N<<1];

void ADD(int u,int v,int w){e[k]=(E){v,head[u],w};head[u]=k++;}

int main()

{

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

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

	go(i,1,t)scanf("%d%d%d",&U,&V,&W),ADD(U,V,W);

	go(i,1,m)

	{

		go(j,0,c[i]-1)val[j]=(a[i]*j+b[i])%c[i]+d[i];

		lef[0]=val[0];rig[c[i]-1]=c[i]-1+val[c[i]-1];

		go(j,1,c[i]-1)lef[j]=min(lef[j-1],val[j]+j);

		ro(j,c[i]-2,0)rig[j]=min(rig[j+1],val[j]+j);

		go(j,0,c[i]-1)D[i][j]=min(lef[j]-j+c[i],rig[j]-j);

	}

	go(i,2,n)dis[i]=1000000000;

	dis[1]=s;q.push(1);int u;

	while(!q.empty())

	{

		inq[u=q.front()]=0;q.pop();

		fo(i,head,u)if(dis[u]+D[e[i].w][dis[u]%c[e[i].w]]<dis[v])

		{

			dis[v]=dis[u]+D[e[i].w][dis[u]%c[e[i].w]];

			!inq[v]?q.push(v),inq[v]=1:1;

		}

	}

	go(i,2,n)printf("%d\n",dis[i]==1000000000?-1:dis[i]-s);return 0;

}//Paul_Guderian

就像这时的我满怀悲伤，唱着这段无人喝彩的旋律……——汪峰《再见蒲公英》

巴特西