暴力

首先，看到这个题我们可以很轻松的想到一个暴力。

令 $f_i$ 为如果要经过第 $i$ 条边则在此之前需要的花费最少为多少。

一个显然的方程式是：

$$f_i=\min(f _j+A\times (p_i-q_j)^2+B\times (p_i-q_j)+C)$$

其中 $j$ 是满足 $y_j=x_i$ 且 $q_j\le p_i$ 的边。

（这边的 $x,y,p,q,A,B,C$ 变量含义全部与题目相同）

我们可以通过将一条边分为出和入两步来更新，从而消除时间顺序的问题。

理论复杂度为 $\operatorname{O}(m^2)$ ，实际上卡不满。

决策单调性

当我们看到这样的一个转移方程式时，我们一定会想到：这个题与决策单调性有关。

令 $w_{q_j,p_i}$ 为从 $j$ 转移到 $i$ 的费用，即 $A\times (p_i-q_j)^2+B\times (p_i-q_j)+C)$。

我们可以证明，对于边 $i_1,i_2$ 如果有 $x_{i1}=x_{i2}$ 且 $p_{i1}\le p_{i2}$，

设两条边的最优决策点分别为 $j_1,j_2$，则 $q_{j1}\le q_{j2}$。

决策单调性的证明一般使用四边形不等式，但在考场上更多使用打表或是盲猜的方法。

对于不知道四边形不等式的同学，建议阅读这篇博客。

当然也可以选择直接记住一个结论：

若某个方程式 $f_i=\min(f_j+w_{i,j})$的转移费用满足 $w_{a,b}+w_{a+1,b+1}\le w_{a+1,b}+w_{a,b+1}$ 时，

该方程的最优决策点（即最佳的 $j$）随 $i$ 非严格单调递增，即满足决策单调性。

那么接下来，我们来证明一下这个题的决策单调性。

$$w_{a,b}+w_{a+1,b+1}\le w_{a+1,b}+w_{a,b+1}$$ $$\Leftrightarrow A\times(a-b)^2+B\times(a-b)+C+A\times(a+1-b-1)^2+B\times(a+1-b-1)+C$$$$\le A\times (a+1-b)^2+B\times (a+1-b)+C+a\times (a-b-1)^2+B\times (a-b-1)+C$$$$\Leftrightarrow 2\times A(a-b)^2\le A\times (a+1-b)^2+A\times (a-b-1)^2$$

令 $t=a-b$

$$\Leftrightarrow 2\times At^2\le A(t+1)^2+A(t-1)^2$$ $$RHS=2At^2+2A\ge 2At^2=LHS$$

证毕。

顾可知，这一方程满足决策单调性，即满足对于边 $i_1,i_2$ 如果有 $x_{i1}=x_{i2}$ 且 $p_{i1}\le p_{i2}$，

设两条边的最优决策点分别为 $j_1,j_2$，则有 $q_{j1}\le q_{j2}$。

斜率优化

斜率优化是决策单调性的一个高级应用，一般在 $f$ 方程仅有一个维度时有效。

不会斜率优化的同学这里推荐一下辰星凌大佬的博客。

我们来考虑对于 $f_i$ 而言，决策点 $j_1$ 比 $j_2$ （$q_{j_1}\ge q_{j_2}$）更优需要满足什么条件。

将方程式展开后移项，得到

$$f_i-Ap_i^2-Bp_i-C=f_j+Aq_j^2-2Ap_iq_j-Bq_j$$

这样移项的好处是，有关于 $j$ 的项全部被移到了右边。

由于 $i$ 是我们已经确定的，所以 $p_i$ 可以看作常量。

根据方程式可知，若 $j_1$ 比 $j_2$ 更优，则需满足

$$f_{j_1}+Aq_{j_1}^2-2Ap_iq_{j_1}-Bq_{j_1} \le f_{j_2}+Aq_{j_2}^2-2Ap_iq_{j_2}-Bq_{j_2}$$$$\Leftrightarrow 2Ap_i(q_{j_1}-q_{j_2})\ge (f_{j_1}+Aq_{j_1}^2-Bq_{j_1})-(f_{j_2}+Aq_{j_2}^2-Bq_{j_2})$$

令

$$X(a)=q_a$$ $$Y(a)=f_{a}+Aq_{a}^2-Bq_{a}$$ $$K(a)=2\times A\times p_i$$ $$B(a)=f_i-Ap_i^2-Bp_i-C$$

于是我们就得到了一个斜率优化的形式。

当 $i$ 固定时，我们 $K(i)$ 也就固定了。

而我们的目标就是让 $B(i)$ 越小越好。

因此，只要 $j_1,j_2$ 满足

$$K(i)\ge \frac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}$$

也就是 $K(i )$ 大于 $(X(j_1),Y(j_1))$ 与 $(X(j_2),Y(j_2))$ 组成的直线，则 $j_1$ 优于 $j_2$。

这其实非常好理解。当 $K(i)<\frac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}$ 时，设 $B$ 点为 $(X(j_1),Y(j_1))$，$A$ 点为 $(X(j_2),Y(j_2))$，

则我们画出来的图如下：

显然此时让直线经过 $A$ 点更优。

而当 $K(i)\ge \frac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}$ 时，图如下：

显然选择 $B$ 点更优。

又由于我们证明了决策单调性，因此从此以后 $A$ 点（也就是 $j_2$） 再无用处。

如果我们用一个双端队列来维护也许有效的决策点，那么这时我们就可以将 $j_2$ 出队。

接着，我们再来考虑什么样的点需要放入队列中。

对于这样的情况，我们发现，无论所求直线的 $K(i)$ 是多少，$B$ 都不会成为最优决策点，

因此我们就可以将 $B$ 出队。

准确的说，当 $\frac{Y(A)-Y(B)}{X(A)-X(B)}\ge \frac{Y(A)-Y(C)}{X(A)-X(C)}$ 时，$B$ 点就不会成为最优决策点，

因为当 $K(i)<\frac{Y(A)-Y(C)}{X(A)-X(C)}$ 时 $A$ 比 $B$ 更优，否则 $C$ 比 $B$ 更优。

其实如果我们把队列中的所有点画出来，应该是这样的：

Code

#include <bits/stdc++.h>
#define ll long long
#define X(T) (q[T])
#define Y(T) (f[T]+a*q[T]*q[T]-b*q[T])
#define K(T) (2*a*p[T])
#define B(T) (f[T]-a*p[T]*p[T]-b*p[T]-c)
//一个好习惯，也方便直接调用
using namespace std;
inline int read(){
	register int x=0;
	register bool f=0;
	register char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return f?-x:x;
}
char cr[200];int tt;
inline void print(register ll x,register char k='\n') {
    if(!x) putchar('0');
    if(x < 0) putchar('-'),x=-x;
    while(x) cr[++tt]=x%10+'0',x/=10;
    while(tt) putchar(cr[tt--]);
    putchar(k);
}
const int maxn=200001;
int n,m,a,b,c,mx;
int p[maxn],q[maxn],u[maxn],v[maxn];
ll f[maxn],ans=114514191981000000ll;
int tl,tl2,he,he2,sz;
deque<int> d[maxn];
//stl 自带双端队列，也可以用 vector 实现
deque<int>::iterator it;
vector<int> st[1001];
vector<int> ed[1001];
//st,ed 分别为某一时刻的出发与到达数组
double slope(int qa,int qb){
    return (1.0*(Y(qa)-Y(qb)))/(1.0*(X(qa)-X(qb)));
    //求斜率
}
signed main(){
//	freopen("route.in","r",stdin);
//	freopen("route.out","w",stdout);
	n=read();m=read();a=read();b=read();c=read();
	for(int i=1;i<=m;++i){
		u[i]=read();v[i]=read();p[i]=read();q[i]=read();
		if(u[i]==n) continue;
		mx=max(mx,q[i]);
		st[p[i]].push_back(i);
		f[i]=1233333333ll;
        //初始化
	}
	d[1].push_back(0);
	f[1]=0;
	for(int i=0;i<=mx;i++){
		for(int j:ed[i]){
            //枚举第 i 时刻到达的边
			sz=d[v[j]].size();
			if(sz==0) {
				d[v[j]].push_back(j);
				continue;
			}
			it=d[v[j]].end();
			it--;
			tl=*it;
			while(sz>1){
				it--;tl2=*it;
                //tl 为队尾，tl2 为队尾第二个数
				if(slope(tl,tl2)<slope(j,tl2)){
					break;
                    //tl2 可能更优
				}
                //j 一定更优，弹出 tl2
				tl=tl2;sz--;
				d[v[j]].pop_back();
			}
			d[v[j]].push_back(j);
		}
		for(int j:st[i]){
            //枚举第 i 时刻出发的边
			sz=d[u[j]].size();
			if(sz==0) continue;
            //这条边出发之前无法到达该点，故这条边无效
			it=d[u[j]].begin();he=*it;
			while(sz>1){
				it++;he2=*it;
                //he 为队首，he2 为队首第二个数
				if(slope(he2,he)>K(j)){
					break;
				}
                //比较一下那条边更优，如果 he2 可以取代 he 则出队
                //此时队首就是最优决策点了
				he=he2;sz--;
				d[u[j]].pop_front();
			}
			f[j]=f[he]+a*(p[j]-q[he])*(p[j]-q[he])+b*(p[j]-q[he])+c;
            //更新 f 函数
			if(v[j]==n) ans=min(ans,f[j]+q[j]);
			ed[q[j]].push_back(j);
		}
	}
	print(ans);
	return 0;
}