空间传送装置 spfa

太空中一共有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号星球到每个星球最少需要的时间。
2<=n<=100000,1<=m<=50,1<=s<=2000,1<=e<=200000，分别表示星球的个数、空间传送装置的种类数、当前的时间以及空间传送装置的个数。
1<=a_i,b_i,c_i,d_i<=2000

分析

注意到即使有时空抖动，每个点仍然是越早到越好。那么我们预处理出模c意义下每种取值的最佳等待时间，然后直接跑spfa就好了。

代码

#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;

const int N=100005;
const LL inf=(LL)1e15;

int n,m,cnt,s,t,tot[55],last[N],trans[55][2005];
bool vis[N];
queue que;
struct edge{int to,next,op;}e[N*2];
struct data{int a,b,c,d;}tr[55];
LL dis[N];

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void addedge(int u,int v,int op)
{
    e[++cnt].to=v;e[cnt].op=op;e[cnt].next=last[u];last[u]=cnt;
}

void spfa()
{
    for (int i=1;i<=n;i++) dis[i]=inf;
    dis[1]=s;que.push(1);vis[1]=1;
    while (!que.empty())
    {
        int u=que.front();que.pop();
        for (int i=last[u];i;i=e[i].next)
            if (dis[u]+trans[e[i].op][(dis[u]-1)%tot[e[i].op]+1]=1;j--)
        {
            int now=(pos+j-1)%tot[i]+1;
            trans[i][now]=min(trans[i][now%tot[i]+1]+1,(tr[i].a*now+tr[i].b)%tr[i].c+tr[i].d);
        }
    }
    spfa();
    for (int i=2;i<=n;i++)
        if (dis[i]==inf) puts("-1");
        else printf("%lld\n",dis[i]-s);
    return 0;
}