【最短路&DP】BZOJ5047空间传送装置

【最短路&DP】BZOJ5047空间传送装置。

太空中一共有n座星球，它们之间可以通过空间传送装置进行转移。空间传送装置分为m种，第i种装置可以用4个参数ai,bi,ci,di来描述。因为时空抖动的问题，在非整数时刻禁止使用空间传送装置。如果在整数s时刻使用装置，那么需要花费((ai?s+bi)modci)+di单位时间才能完成传送。现在是s时刻，小Q位于1号星球，请写一个程序计算从1号星球到每个星球最少需要的时间。

第一行包含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。

分析

设我们可以在i,j两个时间到达某一个点（i
因为这道题的路程消耗与出发时间有关，所以可能会担忧这样会不会i比j还要劣一些。然而其实只要稍加思考，就会发现不存在这样的问题，因为这道题允许等待！i时刻完全可以在原地等到j时刻再出发，这样早到的无论如何都不比晚到的差。这样一来，只要能算出((ai?s+bi)modci)+di在不同s下的最小值，那么这道题就变成了裸的最短路了。
首先，我们很容易想到，我们需要考虑的出发时间只有[0,ci)这个区间，不在这个区间内的，我们把出发时间s mod c_i即可。
那么整个问题就变成了：
统计不同出发时间的分别的路程消耗的最小值。
机制地发现数据范围小了很多：
m<=50,c<=2000
感受到了DP的气息。
首先，我们忽略c-1秒，在0秒到c-2秒中：
对于某个时间t，设其消耗时间为dp[t]，
我们可以选择：
等待一秒，dp[t]=dp[t+1]+1
一秒钟都不等，直接从当前时刻出发：即dp[t]=((ai?t+bi)modci)+di
转移方程很容易理解，那么问题来了，c-1秒怎么解决？
答案是：暴力呗。。。
只有50个c-1秒，我们等待时间也在[0,c?1]的范围内，直接每个等待时间枚举一次就好了嘛（亏cch还想了半天怎么高效地算出c-1的消耗）。

附上代码：（考场上脑残地wa了4次，全是因为输出的时候逗逼了）

#include
#include
#include
#include
#include
#include
#include
#define SF scanf
#define PF printf
#define MAXT 55
#define MAXC 2010
#define MAXN 100010
#define MAXM 200010
using namespace std;
int n,m,tot,dist[MAXN],res;
vector d[MAXN],p[MAXN];
bool inq[MAXN];
int dp[MAXT][MAXC];
queue q;
struct node{
    int a,b,c,d;
}s[MAXT];
void prepare(){
    for(int i=1;i<=tot;i++){
        int st=s[i].c-1;
        for(int j=0;j=0;j--)
            dp[i][j]=min(dp[i][j+1]+1,(j*s[i].a+s[i].b)%s[i].c+s[i].d);
    }
}
void spfa(){
    q.push(1);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        inq[x]=0;
        for(int i=0;idist[x]+t){
                dist[y]=dist[x]+t;
                if(inq[y]==0){
                    q.push(y);
                    inq[y]=1;
                }
            }
        }
    }
}
int main(){
    memset(dp,0x3f,sizeof dp);
    int st;
    memset(dist,-1,sizeof dist);
    SF("%d%d%d%d",&n,&tot,&st,&m);
    int x,y,z;
    for(int i=1;i<=tot;i++){
        SF("%d%d%d%d",&s[i].a,&s[i].b,&s[i].c,&s[i].d);
        s[i].a%=s[i].c;
        s[i].b%=s[i].c;
    }
    prepare();
    for(int i=1;i<=m;i++){
        SF("%d%d%d",&x,&y,&z);
        d[x].push_back(y);
        p[x].push_back(z);
    }
    dist[1]=st;
    spfa();
    for(int i=2;i<=n;i++)
        if(dist[i]==-1)
            PF("-1\n");
        else
            PF("%d\n",dist[i]-st);//注意审题！是需要的时间！不是到达时间！
}