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。

O(mc)递推预处理出每种边在模c意义下x时刻的边长，然后做普通的最短路。

#include<bits/stdc++.h>

typedef unsigned int u32;

const int N=1e5+;

int _(){int x;scanf("%d",&x);return x;}

int n,m,e;

struct edge{

    int to,tp;

    edge*nx;

}es[N*],*ep=es,*e0[N];

struct node{

    u32 w,l;

    bool operator<(const node&w)const{return l>w.l;}

};

std::priority_queue<node>q;

u32 l[N];

void mins(u32&a,u32 b){if(a>b)a=b;}

struct etype{

    u32 a,b,c,d,ds[];

    void read(){

        a=_(),b=_(),c=_(),d=_();

        for(u32 i=;i<c;++i)ds[i]=(a*i+b)%c;

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

            ds[c]=ds[];

            for(u32 i=c;i;--i)mins(ds[i-],ds[i]+);

        }

        for(u32 i=;i<c;++i)ds[i]+=d;

    }

    u32 operator()(u32 x){return ds[x%c];}

}ts[];

int main(){

    n=_();m=_();l[]=_();e=_();

    for(int i=;i<=m;++i)ts[i].read();

    for(int i=,a,b,c;i<=e;++i){

        a=_(),b=_(),c=_();

        *ep=(edge){b,c,e0[a]};e0[a]=ep++;

    }

    for(int i=;i<=n;++i)l[i]=UINT_MAX;

    q.push((node){,l[]});

    while(q.size()){

        node w=q.top();q.pop();

        if(w.l!=l[w.w])continue;

        for(edge*i=e0[w.w];i;i=i->nx){

            u32 u=i->to,d=ts[i->tp](w.l);

            if(l[u]>w.l+d)q.push((node){u,l[u]=w.l+d});

        }

    }

    for(int i=;i<=n;++i)l[i]==UINT_MAX?puts("-1"):printf("%u\n",l[i]-l[]);

    return ;

}