代码

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int mod=998244353;
typedef long long ll;
inline int add(int a,int b)
{
	if((a+=b)>=mod)a-=mod;
	return a;
}
inline int dec(int a,int b)
{
	if((a-=b)<0)a+=mod;
	return a;
}
inline int mult(int a,int b)
{
	long long t=1ll*a*b;
	if(t>=mod)t%=mod;
	return t;
}
inline int power(int a,int b)
{
	int out=1;
	while(b)
	{
		if(b&1)out=mult(out,a);
		a=mult(a,a);
		b>>=1;
	}
	return out;
}
int n,m,A,B,C;
int s[200010],e[200010],p[200010],q[200010];
inline int f(int x)
{
	return A*x*x+B*x+C;
}
vector<int> R[1010];
vector<pair<int,ll> > tb[100010];
priority_queue<pair<int,ll>,vector<pair<int,ll> >,greater<pair<int,ll> > > Q[100010];
void insert(int pos,pair<int,ll> x)
{
	x.second+=A*x.first*x.first-B*x.first;
	while(tb[pos].size()>=2)
	{
		pair<int,ll> p1=tb[pos][tb[pos].size()-2],p2=tb[pos].back(),p3=x;
		if((p3.second-p1.second)*(p2.first-p1.first)<=(p2.second-p1.second)*(p3.first-p1.first))tb[pos].pop_back();
		else break;
	}
	tb[pos].push_back(x);
}
inline ll getval(pair<int,ll> x,int T)
{
	return x.second+1ll*A*T*T-2ll*A*T*x.first+B*T+C;
}
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&A,&B,&C);
	B++;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d%d",&s[i],&e[i],&p[i],&q[i]);
	for(int i=1;i<=m;i++)
	{
		R[p[i]].push_back(i);
	}
	tb[1].push_back(make_pair(0,0));
	for(int T=0;T<=1000;T++)
	{
		for(int j=0;j<R[T].size();j++)
		{
			int id=R[T][j];
			int st=s[id];
			while(!Q[st].empty()&&Q[st].top().first<=T)
			{
				insert(st,Q[st].top());
				Q[st].pop();
			}
			ll mnv;
			if(tb[st].size()==0)continue;
			int l=1,r=tb[st].size()-1,pos=0;
			mnv=getval(tb[st][0],T);
			while(l<=r)
			{
				int mid=(l+r)>>1;
				mnv=min(mnv,min(getval(tb[st][mid],T),getval(tb[st][mid-1],T)));
				if(getval(tb[st][mid],T)>getval(tb[st][mid-1],T))r=mid-1;
				else pos=mid,l=mid+1;
			}
			mnv=min(mnv,getval(tb[st][pos],T));
			Q[e[id]].push(make_pair(q[id],mnv+q[id]-p[id]));
		}
	}
	while(!Q[n].empty())
	{
		insert(n,Q[n].top());
		Q[n].pop();
	}
	ll ans=1e18;
	for(int i=0;i<tb[n].size();i++)ans=min(ans,tb[n][i].second-A*tb[n][i].first*tb[n][i].first+B*tb[n][i].first);
	printf("%lld\n",ans);
//	printf("%lld\n",tb[n][0].second-A*tb[n][0].first*tb[n][0].first+B*tb[n][0].first);
//	getchar();getchar();
	return 0;
}

评测结果