题解

明显可以利用斜率优化加速转移。

但是问题在于路径是一个持续性的过程，即 p
i
​
和 q
i
​
之间可能相距很远。不过我们完全可以将 p
i
​
和 q
i
​
拆成 一次询问 和 一次尾部插入 两个事件，这样事件就可以通过排序变成时间单调递增的了。

接下来考虑 x 和 y ，也就是起点和终点。不过这可以用上面一样的方法处理，也就是将起点和终点拆成两个操作。我们依然维护单调队列，但是因为每个事件对应的地点有区别，因此我们对每个点开一个 vector ，分别维护即可。

记得在 1 号点预先放一个 0 时刻 0 代价的点作为起点。答案可以在路径终点是 n 的时候直接统计，n 号点就没必要再开 vector 了。

时间复杂度瓶颈在排序上。因为数据范围特别小，因此可以直接采用统排。时间复杂度 O(M+T)，其中 T 是时间范围的最大值。

代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
#define il inline
#define vd void
#define rg register
#define mn 100005
#define mp make_pair
#define fr first
#define sd second
#define rep(i,x,y) for(rg int i=x;i<=y;++i)
#define drp(i,x,y) for(rg int i=x;i>=y;--i)
using namespace std;
const int Len=2333333;
char buf[Len],*p1=buf,*p2=buf,duf[Len],*q1=duf;
il char gc(); il int rd(); il vd pc(char c); il vd rt(int x); il vd flush();
template<class T> il T Max(T a,T b){return a>b?a:b;}
template<class T> il T Min(T a,T b){return a<b?a:b;}
int n,m,A,B,C,cry,ans=0x7fffffff;
vector <pair<int,int> > Q[mn<<1],K[1005];
il int Wind(int y,int o,int q,int ny){
    return 1ll*(Q[y][o].sd-Q[y][o-1].sd)*(q-Q[y][o].fr)>=1ll*(ny-Q[y][o].sd)*(Q[y][o].fr-Q[y][o-1].fr);
}
il vd Push(int y,int q,int ny){
    if(!Q[y].empty()&&q==Q[y][Q[y].size()-1].fr){
        if(ny<Q[y][Q[y].size()-1].sd) Q[y].pop_back(); else return;
    }
    while(Q[y].size()>1&&Wind(y,Q[y].size()-1,q,ny)) Q[y].pop_back(); //特判横坐标相同
    Q[y].push_back(mp(q,ny));
}
struct L{
    int x,y,p,q;
    il int operator <(const L &pp)const{return p<pp.p;}
    il vd in(){x=rd(),y=rd(),p=rd(),q=rd();}
    il int Check(int o){return Q[x][o+1].sd-Q[x][o].sd>=A*p*(Q[x][o+1].fr-Q[x][o].fr)<<1;}
    il vd Work(){
        while(cry<p){
            ++cry;
            for(rg int i=0;i<(int)K[cry].size();++i) Push(K[cry][i].fr,cry,K[cry][i].sd);
        } //加点
        if(Q[x].empty()) return;
        int l=0,r=Q[x].size()-2,ps=r+1,mid;
        while(l<=r) if(Check(mid=(l+r)>>1)) ps=mid,r=mid-1; else l=mid+1; //二分
        int d=Q[x][ps].sd-(A*p*Q[x][ps].fr<<1)+A*p*p+B*p+C;
        K[q].push_back(mp(y,d+A*q*q-B*q)); // 暂存在该时刻的vector里
        if(y==n) ans=Min(ans,d+q);
    }
}l[mn<<1];
int main(){
    n=rd(),m=rd(),A=rd(),B=rd(),C=rd();
    rep(i,1,m) l[i].in();
    sort(l+1,l+m+1),Q[1].push_back(mp(0,0)); //0时刻在1号点
    rep(i,1,m) l[i].Work();
    rt(ans);
    return flush(),0;
}

il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,Len,stdin),p1==p2)?-1:*p1++;}
il int rd(){char c;
    while(!isdigit(c=gc())&&c!='-');
    int f=c=='-'?c=gc(),1:0,x=c^48;
    while(isdigit(c=gc())) x=((x+(x<<2))<<1)+(c^48);
    return f?-x:x;
}
il vd pc(char c){q1==duf+Len&&fwrite(q1=duf,1,Len,stdout),*q1++=c;}
il vd rt(int x){x<0?pc('-'),x=-x:0,pc((x>=10?rt(x/10),x%10:x)+48);}
il vd flush(){fwrite(duf,1,q1-duf,stdout);}