代码

#include<bits/stdc++.h>
#define ll long long
#define L(i,l,r) for(int i=(l);i<=(r);++i)
#define R(i,r,l) for(int i=(r);i>=(l);--i)
const int maxbuf=1<<21;
char buf[maxbuf],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,maxbuf,stdin),p1==p2)?EOF:*p1++)
//#define GC getchar()
inline int rei(void) {
	int x=0;
	int flag=0;
	char c=GC;
	while((c<'0'||c>'9')&&c!='-')c=GC;
	if(c=='-')flag=1,c=GC;
	while(c>='0'&&c<='9')x=x*10+c-48,c=GC;
	return flag?-x:x;
}
const int maxlim=1<<20;
char pbuf[maxbuf],*pp=pbuf;
inline void _main(void) {
	return fwrite(pbuf,1,pp-pbuf,stdout),pp=pbuf,void();
}
inline void wri(int x) {
	if(pp-pbuf>maxlim)_main();
	if(x<0)x=-x,*pp++='-';
	static int ws[64];
	int top=0;
	do {
		ws[++top]=x%10,x/=10;
	} while(x);
	while(top)*pp++=ws[top--]+'0';
	return ;
}
namespace yihlaushih {
	int n,m,A,B,C;
	const int maxn=1e5+5;
	const int maxm=2e5+5;
	struct staT {
		int x,y,p,q;
		inline bool operator<(const staT &b)const {
			return p==b.p?q<b.q:p<b.p;
		}
	} s[maxm];
	const int inf=0x3f3f3f3f;
	const int maxx=1e3;
	const int maxt=10000005;
	int tot,rt[maxn];
	int ls[maxt],rs[maxt],x[maxt],y[maxt];
	inline void segmodify(int&rt,int l,int r,int a,int b) {
		if(!rt) {
			rt=++tot,x[rt]=a,y[rt]=b,ls[rt]=rs[rt]=0;
			return ;
		}
		if(x[rt]>=a&&y[rt]>=b) {
			x[rt]=a,y[rt]=b;
			return ;
		}
		if(x[rt]<=a&&y[rt]<=b)return ;
		double X=1.0*(y[rt]-b)/(a-x[rt]);
		if(X<=l) {
			if(x[rt]>=a)x[rt]=a,y[rt]=b;
			return ;
		}
		if(r<=X) {
			if(x[rt]<=a)x[rt]=a,y[rt]=b;
			return ;
		}
		int mid=l+r>>1;
		if(X<=mid) {
			if(x[rt]>=a)std::swap(x[rt],a),std::swap(y[rt],b);
			segmodify(ls[rt],l,mid,a,b);
		} else {
			if(x[rt]<=a)std::swap(x[rt],a),std::swap(y[rt],b);
			segmodify(rs[rt],mid+1,r,a,b);
		}
		return ;
	}
	inline int segquery(int rt,int l,int r,int x) {
		if(!rt)return inf;
		int ret=yihlaushih::x[rt]*x+y[rt];
		if(l==r)return ret;
		int mid=l+r>>1;
		if(x<=mid) {
			return std::min(ret,segquery(ls[rt],l,mid,x));
		}
		return std::min(ret,segquery(rs[rt],mid+1,r,x));
	}
	struct dij {
		int tim,x,dis;
		inline dij(int a=0,int b=0,int c=0):tim(a),x(b),dis(c) {}
		inline bool operator<(const dij &b)const {
			return tim>b.tim;
		}
	};
	std::priority_queue<dij > q;
	inline int a114514suns(void) {
//		freopen("route.in","r",stdin);
//		freopen("route.out","w",stdout);
		n=rei(),m=rei(),A=rei(),B=rei(),C=rei();
		L(i,1,m)s[i].x=rei(),s[i].y=rei(),s[i].p=rei(),s[i].q=rei();
		std::sort(s+1,s+1+m);
		int j=0,ans=inf;
		segmodify(rt[1],1,maxx,0,0);
		L(t,0,maxx) {
			while(q.size()&&q.top().tim<=t) {
				int x=q.top().x,sq=q.top().tim,f=q.top().dis;
				q.pop();
				if(x==n) {
					ans=std::min(ans,sq+f);
				} else {
					segmodify(rt[x],1,maxx,-2*A*sq,f+A*sq*sq-B*sq);
				}
			}
			while(j<m&&s[j+1].p<=t) {
				++j;
				int val=segquery(rt[s[j].x],1,maxx,s[j].p)+A*s[j].p*s[j].p+B*s[j].p+C;
				if(val<inf)q.push(dij(s[j].q,s[j].y,val));
			}
		}
//		printf("%d\n",tot);
		printf("%d\n",ans);
		return _main(),0;
	}
}
int main() {
	return yihlaushih::a114514suns(),0;
}

评测结果