下面是我的斜率优化

这种写法不能正确维护凸包

但交上去却AC了

我直到今天才发现我的智障写法是错的……

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
long long n,m,A,B,C,NUMIN,PIN,ans,tail[100010];
char CI;
struct FOR_q
{
	long long f,t;
	bool operator < (const FOR_q & a1) const
	{
		return t>a1.t;
	}
}nq;
priority_queue<FOR_q> q[100010];
vector <FOR_q> v[100010];
inline long long read()
{
	NUMIN=0,PIN=1;
	CI=0;
	while(CI<'0'||CI>'9'){if(CI=='-') PIN=-1;CI=getchar();}
	while(CI>='0'&&CI<='9'){NUMIN=NUMIN*10+CI-'0';CI=getchar();}
	return NUMIN*PIN;
}
struct EDGE
{
	long long from,to,ft,tt;
}e[1000010];
inline bool cmp(const EDGE a1,const EDGE a2)
{
	return a1.ft<a2.ft;
}
inline long long js(FOR_q a1,long long q)
{
	return a1.f+A*a1.t*a1.t-B*a1.t-(long long)2*A*q*a1.t;
}
inline long long min(long long a1,long long a2)
{
	return a1<a2 ? a1 : a2;
}
int main()
{
	//freopen("in.txt","r",stdin);
	n=read();m=read();A=read();B=read();C=read();
	ans=(long long)1e16;
	for(int i=1;i<=n;i++)
		tail[i]=1;
	for(int i=1;i<=m;i++)
	{
		e[i].from=read();e[i].to=read();e[i].ft=read();e[i].tt=read();
	}
	sort(e+1,e+m+1,cmp);
	nq.t=nq.f=0;
	q[1].push(nq);
	for(int i=1;i<=m;i++)
	{
		while(!q[e[i].from].empty() && q[e[i].from].top().t<=e[i].ft)
		{
			nq=q[e[i].from].top();
			q[e[i].from].pop();
			while(v[e[i].from].size()>=tail[e[i].from] && js(v[e[i].from].back(),e[i].ft)>=js(nq,e[i].ft))
				v[e[i].from].pop_back();
			v[e[i].from].push_back(nq);
			while(v[e[i].from].size()>tail[e[i].from] && js(v[e[i].from][tail[e[i].from]-1],e[i].ft)>=js(v[e[i].from][tail[e[i].from]],e[i].ft))
				tail[e[i].from]++;
		}
		if(tail[e[i].from]<=v[e[i].from].size())
		{
			nq.f=js(v[e[i].from][tail[e[i].from]-1],e[i].ft)+A*e[i].ft*e[i].ft+B*e[i].ft+C;
			nq.t=e[i].tt;
			q[e[i].to].push(nq);
			if(e[i].to==n)
				ans=min(ans,nq.f+nq.t);
		}
	}
	cout<<ans;
	return 0;
}