代码

#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
#define Dor(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
using namespace std;
const int N=100007,M=400007;
int n,m,T[N];
LL a,b,c,F[M];
struct D {
	int x,y,p,q;
	bool operator < (const D &_) const {
		return p<_.p;
	}
}A[M];
struct G {
	LL x,y;
	bool operator < (const G &_) const {
		if(x==_.x) return y>_.y;
		return x>_.x;
	}
};
vector<G> V[N];
priority_queue<G> W[N];
bool beng(G a,G b,G c) {
	return 1.*(b.y-a.y)*(c.x-b.x)>=1.*(c.y-b.y)*(b.x-a.x);
}
void Ins(vector<G> &S,int &tp,G x) {
	while(tp>1&&beng(S[tp-1],S[tp],x)) --tp;
	if(tp>1&&S[tp].x==x.x) return;
	++tp;
	while((int)S.size()<=tp) S.push_back((G){0,0});
	S[tp]=x;
}
LL Qry(vector<G> &S,int &tp,LL k) {
	while(tp>1&&k*S[tp-1].x+S[tp-1].y<=k*S[tp].x+S[tp].y) --tp;
	if(tp) return k*S[tp].x+S[tp].y;
	return 0;
}
int main() {
	memset(F,60,sizeof(F));
	LL ans=F[0];
	scanf("%d%d%lld%lld%lld",&n,&m,&a,&b,&c);
	For(i,1,m) scanf("%d%d%d%d",&A[i].x,&A[i].y,&A[i].p,&A[i].q);
	sort(A+1,A+1+m);
	For(i,1,m) {
		int u=A[i].x,p=A[i].p,q=A[i].q;
		if(u==1) F[i]=a*p*p+b*p+c;
		while(!W[u].empty()&&W[u].top().x<=p) {
			Ins(V[u],T[u],W[u].top());
			W[u].pop();
		}
		F[i]=min(F[i],Qry(V[u],T[u],-2*a*p)+a*p*p+b*p+c);
		W[A[i].y].push((G){q,a*q*q-b*q+F[i]});
	}
	For(i,1,m)
	if(A[i].y==n) ans=min(ans,F[i]+A[i].q);
	printf("%lld",ans);
	return 0;
}

评测结果