太空中一共有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号星球到每个星球最少需要的时间。
题解：需要发现两个很重要的性质，如果在s时刻到达了某条边的起点，则通过这条边的最短时间是固定的。并且，s越早，通过的时间一定不会越晚，这就意味着在跑最短路时，Dijkstra的贪心策略是行得通的。
所以可以先预处理出f[i][j]代表在j时刻想要通过种类为i的边，所需要的最短时间是多少。因为有%c[i]的存在，所以j最多为3000。我们用前缀和后缀最大值来处理f数组即可。然后就能跑Dij了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#define mp(A,B) make_pair(A,B)
using namespace std;
typedef pair<int,int> 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<pii> 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<C[i];j++) val[j]=(A[i]*j+B[i])%C[i]+D[i];
tmp1[0]=val[0],tmp2[C[i]-1]=C[i]-1+val[C[i]-1];
for(j=1;j<C[i];j++) tmp1[j]=min(tmp1[j-1],j+val[j]);
for(j=C[i]-2;j>=0;j--) tmp2[j]=min(tmp2[j+1],j+val[j]);
for(j=0;j<C[i];j++) T[i][j]=min(C[i]-j+tmp1[j],tmp2[j]-j);
}
memset(head,-1,sizeof(head)),memset(dis,0x3f,sizeof(dis));
for(i=1;i<=E;i++) a=rd(),b=rd(),c=rd(),add(a,b,c);
dis[1]=S;
q.push(mp(-S,1));
while(!q.empty())
{
u=q.top().second,q.pop();
if(vis[u]) continue;
vis[u]=1;
for(i=head[u];i!=-1;i=next[i])
{
if(dis[to[i]]>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
原文：http://www.cnblogs.com/CQzhangyu/p/7587308.html