记录编号	612624	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2019]回家路线	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	1.030 s
提交时间	2026-02-25 13:28:18	内存使用	8.78 MiB

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int M=1e6+10,V=1e3,N=1e5+10;
const int inf=1e18;
int n,m,A,B,C,p[M],q[M],x[M],y[M],f[M],ans;
int k[M],b[M],rt[N],mx[M<<1],ls[M<<1],rs[M<<1],cnt;
pii id[M];
priority_queue<pii>pq;
void calc(int i){k[i]=-2*q[i]*A,b[i]=A*q[i]*q[i]-B*q[i]+f[i];}
int val(int i,int v){return k[i]*v+b[i];}
void upd(int &p,int l,int r,int v){
	if(!p)p=++cnt;if(!mx[p]){mx[p]=v;return;}
	if(val(v,l)<val(mx[p],l)&&val(v,r)<val(mx[p],r)){mx[p]=v;return;}
	if(val(v,l)>val(mx[p],l)&&val(v,r)>val(mx[p],r))return;
	int mid=(l+r)>>1;
	if(val(v,mid)<val(mx[p],mid))swap(v,mx[p]);
	if(val(v,l)<val(mx[p],l))upd(ls[p],l,mid,v);
	if(val(v,r)<val(mx[p],r))upd(rs[p],mid+1,r,v);
}
int ask(int p,int l,int r,int v){
	if(!p)return inf;int res=val(mx[p],v);
	if(l==r)return res;int mid=(l+r)>>1;
	if(v<=mid)return min(res,ask(ls[p],l,mid,v));
	if(v>mid)return min(res,ask(rs[p],mid+1,r,v));
}
signed main(){
	b[0]=ans=inf;
	scanf("%lld %lld %lld %lld %lld",&n,&m,&A,&B,&C);
	for(int i=1;i<=m;i++){
		scanf("%lld %lld %lld %lld",x+i,y+i,p+i,q+i);
		id[i]=mp(p[i],i),f[i]=inf;
	}
	sort(id+1,id+1+m);
	for(int o=1;o<=m;o++){
		int i=id[o].se;
		if(x[i]==1){
			f[i]=A*p[i]*p[i]+B*p[i]+C;
		}else{
			while(pq.size()){
				if(-pq.top().fi<=p[i]){
					int j=pq.top().se;pq.pop();
					calc(j);upd(rt[y[j]],0,V,j);
				}else break;
			}
			f[i]=ask(rt[x[i]],0,V,p[i])+A*p[i]*p[i]+B*p[i]+C;
		} 
		pq.push(mp(-q[i],i));
	}
	for(int i=1;i<=m;i++){
		if(y[i]==n)ans=min(ans,f[i]+q[i]);
	}
	printf("%lld\n",ans);
	return 0;
}