如题

#include<cstdio>
#include<vector>
const int LIMIT_TIME=40000;
const int MAXN=1e6;
const long double eps=1e-11;
const long long inf=0x3f3f3f3f3f3f3f3fll;
int n,m,A,B,C;
struct edge{
	int u,v,s,t;
	edge(int _u,int _v,int _s,int _t):u(_u),v(_v),s(_s),t(_t){}
};
std::vector<edge>q1[LIMIT_TIME+86];
struct item{
	int u,x;
	long long f;
	item(int _u,int _x,long long _f):u(_u),x(_x),f(_f){}
};
std::vector<item>q2[LIMIT_TIME+86];
struct lower_convex_hull{
	struct point{
		int x;
		long long y;
		point(int _x,long long _y):x(_x),y(_y){}
	};
	friend long double get_k(const point& p0,const point& p1)
	{
		if(p1.x==p0.x)
			return p1.y>p0.y?1e20:-1e20;
		return static_cast<long double>(p1.y-p0.y)/(p1.x-p0.x);
	}
	friend long long get_b(const point& p,long long k)
	{
		return p.y-k*p.x;
	}
	friend bool is_lower(const point& p0,const point& p1,const point& p2)
	{
		return get_k(p0,p1)-get_k(p0,p2)>eps;
	}
	std::vector<point>contain;
	int head;
	lower_convex_hull():head(0),contain(){}
	void insert(const item& val)
	{
		point val_p(val.x,1ll*A*val.x*val.x-(B+1)*val.x+val.f);
		while(contain.size()-head>1&&is_lower(contain[contain.size()-2],contain[contain.size()-1],val_p))
			contain.pop_back();
		if(contain.size()-head==1&&contain[contain.size()-1].y>val_p.y)
			contain.pop_back();
		contain.push_back(val_p);
	}
	long long query(int s,int t)
	{
		long long k=2*A*s;
		if(head>=contain.size())
			return -inf;
		while(head<contain.size()-1&&get_b(contain[head],k)>get_b(contain[head+1],k))
			head++;
		return get_b(contain[head],k)+1ll*A*s*s+1ll*B*s+C+t;
	}
}lch[MAXN+86];
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);
	while(m--)
	{
		int u,v,s,t;
		scanf("%d%d%d%d",&u,&v,&s,&t);
		q1[s].push_back(edge(u,v,s,t));
	}
	long long res=0x3f3f3f3f3f3f3f3fll;
	q2[0].push_back(item(1,0,0));
	for(int i=0;i<=LIMIT_TIME;i++)
	{
		for(item now:q2[i])
			lch[now.u].insert(now);
		for(edge now:q1[i])
		{
			long long new_f=lch[now.u].query(now.s,now.t);
			if(new_f==-inf)
				continue;
			if(now.v==n&&res>new_f)
				res=new_f;
			q2[now.t].push_back(item(now.v,now.t,new_f));
		}
	}
	printf("%lld",res);
	return 0;
}