代码

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<set>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
namespace Fread{
	char buffer[32768],*cs,*ct;
	#define get_char (cs==ct&&(ct=(cs=buffer)+fread(buffer,1,32768,stdin),cs==ct)?0:*cs++)
	inline int read(){
		register int x=0;
		register char c=get_char;
		while(c<'0'||c>'9') c=get_char;
		while(c>='0'&&c<='9') x=x*10+(c^48),c=get_char;
		return x;
	}
	#undef getc
}
using namespace Fread;
struct data{
	int x,y;
	LL p,q;
//	int id;
}t[1000006];
int n,m;
LL A,B,C;
LL f[1000005];
LL X[1000001],Y[1000001];
std::vector<int>q[1000001];
struct cmp{
	inline int operator()(const int &aa,const int &bb){
		return t[aa].q==t[bb].q?aa>bb:t[aa].q<t[bb].q;
	}
};
struct _insert{
	int i;
	inline int operator <(const _insert &a)const{return t[i].q>t[a.i].q;}//按 q 的升序
};
std::priority_queue<_insert>insert[1000001];
inline int cmp(data a,data b){return a.p<b.p;}
inline LL min(LL a,LL b){return a>b?b:a;}
//inline LL X(int i){return t[i].q;}
//inline LL Y(int i){return f[i]+A*t[i].q*t[i].q-B*t[i].q;}
inline void Insert(int i){
	reg int size,j,head;//size 为 set insert 的大小，head 为 vector q[x[i]] 最后一个数的下标
	size=insert[t[i].x].size();
	if(!size) return;
	j=insert[t[i].x].top().i;
	while(size&&t[j].q<=t[i].p){
		head=q[t[i].x].size()-1;
		while(head>0){
			if((Y[q[t[i].x][head]]-Y[q[t[i].x][head-1]])*(X[j]-X[q[t[i].x][head]])
			>=(Y[j]-Y[q[t[i].x][head]])*(X[q[t[i].x][head]]-X[q[t[i].x][head-1]])) q[t[i].x].pop_back();
			else break;
			head--;
		}
		q[t[i].x].push_back(j);
		size--;insert[t[i].x].pop();
		j=insert[t[i].x].top().i;
	}
}
inline void pop(int i){
	reg int size=q[t[i].x].size();
	reg LL K=2*A*t[i].p;
	while(size>1&&Y[q[t[i].x][1]]-Y[q[t[i].x][0]]<=K*(X[q[t[i].x][1]]-X[q[t[i].x][0]])){
		size--;
		q[t[i].x].erase(q[t[i].x].begin());
	}
}
int main(){
//		std::freopen("P6302_2.in","r",stdin);
//		std::freopen("tmp.txt","w",stdout);
	n=read();m=read();A=read();B=read();C=read();
	for(reg int i=1;i<=m;i++)
		t[i].x=read(),t[i].y=read(),t[i].p=read(),t[i].q=read(),f[i]=1e10;
	std::sort(t+1,t+1+m,cmp);
	f[0]=0;
	q[1].push_back(0);
	for(reg int i=1,j;i<=m;i++){//k=2*A*p[i]
		Insert(i);pop(i);
		if(q[t[i].x].size()){
			j=q[t[i].x][0];
			f[i]=f[j]+A*(t[i].p-t[j].q)*(t[i].p-t[j].q)+B*(t[i].p-t[j].q)+C;
			insert[t[i].y].push((_insert){i});
		}
		X[i]=t[i].q;Y[i]=f[i]+A*t[i].q*t[i].q-B*t[i].q;
//			if(f[i]<0){
//				std::printf("i: %d, f[i]: %lld, from: j: %d, f[j]: %lld\n",i,f[i],j,f[j]);
//				std::printf("%d: start : %lld, end : %lld\n%d: start : %lld, end : %lld\n",i,t[i].p,t[i].q,j,t[j].p,t[j].q);
//				if(t[j].q>t[i].p) std::puts("!!! q[j]>p[i] !!!");
//				return 0;
//			}
	}
	LL ans=1e18;
	for(reg int i=1;i<=m;i++)if(t[i].y==n) ans=min(ans,f[i]+t[i].q);
//		for(reg int i=1;i<=m;i++) std::printf("%lld\n",f[i]);
	std::printf("%lld",ans);
	return 0;
}

评测结果