欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ5047
题意概括
概括？？~别为难语文做一题错两题的我了……
题解
我们发现，对于某一种装置，有c种不同的时刻的花费是不同的。
对于s mod c不同的，花费也不一定相同。
但是有一点是一定可以确定的：对于s1<s2，从如果可以从s1开始，一定不比s2差，因为s1可以转移到s2时刻。
我考虑预处理一个数组gt(变量名瞎捏的),gt[i][j]表示第i个机器，从第j个时刻出发，最快可以在哪个时刻到。其中i<=m,0<=j<c[i]。
那么显然有一个大力的m*c2的算法来求gt。注意，如果你等待c秒及以上，则一定是亏的。
然而，实际上，我们只需要大力求解gt[i][c-1]即可，对于gt[i][j]（0<=j<c-1），我们可以考虑有两种选择：一种是当前时刻转移，一种是当前时刻不转移。显然，当前时刻不转移，答案就是gt[i][j+1]，当前时刻转移的话，可以直接算。所以复杂度去掉了一个2000.
当然，用O(m*c2)的算法还是可以过去的，而O(m*c)当然可以更快。
接下来就是大力跑SPFA就可以了。
注意输出时候的-1.
代码
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int N=100000+5,M=50+5,E=200000+5,T=2000+5,Inf=700000000;
struct Gragh{
int cnt,x[E],y[E],z[E],nxt[E],fst[N];
void set(){
cnt=0;
memset(fst,0,sizeof fst);
}
void add(int a,int b,int c){
x[++cnt]=a,y[cnt]=b,z[cnt]=c,nxt[cnt]=fst[a],fst[a]=cnt;
}
}g;
struct Mac{
int a,b,c,d;
}ma[M];
int n,m,e,s,gt[M][T],dis[N];
bool f[N];
queue <int> q;
int main(){
scanf("%d%d%d%d",&n,&m,&s,&e);
for (int i=1;i<=m;i++){
scanf("%d%d%d%d",&ma[i].a,&ma[i].b,&ma[i].c,&ma[i].d);
int a=ma[i].a,b=ma[i].b,c=ma[i].c,d=ma[i].d;
for (int j=0;j<c;j++)
gt[i][j]=1e9;
for (int j=0;j<c;j++){
int now=c-1+j;
gt[i][c-1]=min(gt[i][c-1],now+(a*now+b)%c+d);
}
for (int j=c-2;j>=0;j--)
gt[i][j]=min(gt[i][j+1],j+(a*j+b)%c+d);
}
g.set();
for (int i=1,a,b,c;i<=e;i++){
scanf("%d%d%d",&a,&b,&c);
g.add(a,b,c);
}
for (int i=1;i<=n;i++)
dis[i]=1e9;
memset(f,0,sizeof f);
dis[1]=s;
while (!q.empty())
q.pop();
q.push(1);
f[1]=1;
while (!q.empty()){
int x=q.front();
q.pop();
f[x]=0;
for (int i=g.fst[x];i;i=g.nxt[i]){
int y=g.y[i],z=g.z[i],mo=dis[x]%ma[z].c;
int gtime=dis[x]-mo+gt[z][mo];
if (dis[y]>gtime){
dis[y]=gtime;
if (!f[y]){
f[y]=1;
q.push(y);
}
}
}
}
for (int i=2;i<=n;i++)
if (dis[i]<Inf)
printf("%d\n",dis[i]-s);
else
printf("-1\n");
return 0;
}