自动搬运

查看原文

来自洛谷，原作者为

	WarningQAQ 私永遠に百鬼あやめが好きです

搬运于2025-08-24 22:02:31，当前版本为作者最后更新于2020-09-07 17:53:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：

给出一些车的班次，包括起点，终点，到达起点时间区间，到达终点时间区间，想要$T$时刻到达$n$号点，问最坏情况下的最短等待时间。

题解：

我们可以将问题转化为中间乘坐公交的最长时间。然后我们对于每条边我们把它当成在 $a$ 时刻出发，中间乘坐时间为 $c-b$ ，到达时间为d的一条线路。然后你就可以想到一个 $O(NM)$ 的动归, $f(i,j)$ 表示在 $j$ 时刻到达 $i$ 的左右，答案 当然那一定是 TLE+MLE ，于是我们考虑优化。我们发现原方程有两种转移：

1： $f(i,j) = f(i,j-1)$

2： $f(i,j) = f(k,l) + dis$ （有一条边）

我们在滚掉第一维之后就发现真正有用的转移只有 $m$ 次，我们将每条路拆分为两个点， $a$ 点处理答案保存， $d$ 点处理最长路的计算，按照时间节点排序，顺序求最长路，我们直接排个序就可以了，注意排序的关键字。 新的状态转移：

1： $ans(id(i)) = f(x(i))$ ; $dis(i)>0$ ;

2： $f(x(i))=$ $max( f(x(i)) , ans(id(i)) + f(i) )$ ;

代码：

#include"bits/stdc++.h"
#define N 50005
using namespace std;
char ch[N*4];
char *Q,*T;
inline char gc(){//快读加fread，快上加快
    if(Q==T){
        T=(Q=ch)+fread(ch,1,N*4,stdin);
        if(Q==T)return EOF;
    }
    return *Q++;
}
inline int read(){//快读主体
    int f=0;
    char c=gc();
    for(;c<'0'||c>'9';c=gc());
    for(;c>='0'&&c<='9';c=gc())f=(f<<1)+(f<<3)+c-48;
    return f;
}
int n=read(),m=read(),tt=read(),t=read(),x,y,a,b,c,d,tot;//由于懒得再打一遍，直接在定义的时候读入了
int dis[N],ans[N*2];
struct ask{
	int x,t,id,dis;
}q[N*4];
bool cmp(const ask&a,const ask&b){//注意排序的依据
    return a.t==b.t?a.dis>b.dis:a.t<b.t;
}
int main(){
    for(int i=1;i<=m;i++){//建图
        x=read();y=read();a=read();b=read();c=read();d=read(); 
        q[++tot]=(ask){x,a,i,0};
        q[++tot]=(ask){y,d,i,c-b};
    }
    q[++tot]=(ask){n+1,t,0,-0x3f3f3f3f};//边界
    sort(q+1,q+tot+1,cmp);
    memset(dis,233,sizeof(dis));
    dis[1]=0;
    for (int i=1;i<=tot;i++){
        if(q[i].x==n+1)break;//如果已经出界，直接跳出
        if(!q[i].dis)ans[q[i].id]=dis[q[i].x];//dp
        else dis[q[i].x]=max(dis[q[i].x],ans[q[i].id]+q[i].dis);
    }
    return printf("%d",dis[tt]<0?-1:t-dis[tt]),0;//集return和输出+判断于一体
}