我是对路线DP，按时间排序，开始时计算答案，结束后加入，然后斜率优化，原题过了，但不知道为什么一直只有72分

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ldb long double
const ll INF=1e18;
using namespace std;

const int N=1e5+5,M=1e6+5;
int n,m,A,B,C;
ll f[M];
struct BB{int x; ll y; };
deque<BB>q[N];
struct AA{int x,t,id; }a[M<<1];
bool cmp(AA i,AA j) {
	return i.t<j.t;
}
signed main() {
//	freopen("1.in","r",stdin);
	scanf("%lld%lld%lld%lld%lld",&n,&m,&A,&B,&C);
	int cnt=0;
	for(int i=1;i<=m;i++) {
		int x,y,p,q; scanf("%lld%lld%lld%lld",&x,&y,&p,&q);
		a[++cnt]=(AA){x,p,i};
		a[++cnt]=(AA){y,q,-i};
		f[i]=INF;
	}
	sort(a+1,a+cnt+1,cmp);
	ll ans=INF;
	for(int i=1;i<=cnt;i++) {
		if(a[i].id<0) {
			if(f[-a[i].id]==INF) continue;
			int x=a[i].x,top=q[x].size(); ll y=f[-a[i].id]+(ll)A*a[i].t*a[i].t-(ll)B*a[i].t;
			while(top>1&&((ldb)(q[x][top-1].y-q[x][top-2].y)*(a[i].t-q[x][top-1].x)>=(ldb)(y-q[x][top-1].y)*(q[x][top-1].x-q[x][top-2].x))) {
				top--;
				q[x].pop_back();
			}
			q[x].push_back((BB){a[i].t,y});
			if(a[i].x==n) ans=min(ans,f[-a[i].id]+a[i].t);
		} else {
			if(a[i].x==1) f[a[i].id]=(ll)A*a[i].t*a[i].t+(ll)B*a[i].t+C;
			int k=2ll*A*a[i].t,x=a[i].x,top=q[x].size();
			while(top>1&&(q[x][1].y-q[x][0].y)<=(ll)k*(q[x][1].x-q[x][0].x)) {
				top--; 
				q[x].pop_front();
			}
			if(top) {
			//	if(a[i].id==4) cout<<q[x][0].x<<' '<<q[x][0].y<<endl;
				f[a[i].id]=min(f[a[i].id],q[x][0].y-(ll)k*q[x][0].x+(ll)A*a[i].t*a[i].t+(ll)B*a[i].t+C);
			}
		}
	}
//	for(int i=1;i<=m;i++) cout<<f[i]<<' ';
//	puts("");
	cout<<ans<<endl;
	return 0;
}

如果markdown挂了可以去提交记录里查看