【BZOJ5047】空间传送装置

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。

题解：需要发现两个很重要的性质，如果在s时刻到达了某条边的起点，则通过这条边的最短时间是固定的。并且，s越早，通过的时间一定不会越晚，这就意味着在跑最短路时，Dijkstra的贪心策略是行得通的。

所以可以先预处理出f[i][j]代表在j时刻想要通过种类为i的边，所需要的最短时间是多少。因为有%c[i]的存在，所以j最多为3000。我们用前缀和后缀最大值来处理f数组即可。然后就能跑Dij了。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define mp(A,B) make_pair(A,B)using namespace std;typedef pair
           
             pii;int n,cnt,m,S,E;int A[2010],B[2010],C[2010],D[2010],head[100010],val[200010],T[55][2010],tmp1[2010],tmp2[2010];int dis[100010],vis[100010],to[200010],next[200010];priority_queue
            
              q;inline void add(int a,int b,int c){ to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;}inline int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f;}int main(){ n=rd(),m=rd(),S=rd(),E=rd(); int i,j,a,b,c,u; for(i=1;i<=m;i++) { A[i]=rd(),B[i]=rd(),C[i]=rd(),D[i]=rd(); for(j=0;j
             
              =0;j--) tmp2[j]=min(tmp2[j+1],j+val[j]); for(j=0;j
              
               dis[u]+T[val[i]][dis[u]%C[val[i]]]) { dis[to[i]]=dis[u]+T[val[i]][dis[u]%C[val[i]]]; q.push(mp(-dis[to[i]],to[i])); } } } for(i=2;i<=n;i++) { if(dis[i]==0x3f3f3f3f) printf("-1\n"); else printf("%d\n",dis[i]-S); } return 0;}//3 2 1 3 1 1 5 1 2 2 7 1 1 2 1 2 3 2 3 1 1