[NOI2019]回家路线（最短路，斜率优化）
终于把这鬼玩意弄完了……
为什么写的这么丑……
（顺便吐槽 routesea）
最短路的状态很显然：(f[i]) 表示从第 (i) 条线下来的最小代价。
首先明显要把那个式子拆开。直觉告诉我们这应该是个斜率优化。
[f[i]=min(f[j]+A(p_i-q_j)^2+B(p_i-q_j)+C)(x_i=y_j,p_ige q_j)
]
[f[i]=min(f[j]+Ap_i^2-2Ap_iq_j+Aq_j^2+Bp_i-Bq_j+C)(x_i=y_j,p_ige q_j)
]
[f[i]=Ap_i^2+Bp_i+C+min((-2Aq_j) imes p_i+(Aq_j^2-Bq_j+f[j]))(x_i=y_j,p_ige q_j)
]
后面是个明显的斜率优化。（说是明显然而同步赛时 SB 了居然没看出来）
然而具体怎么搞？我的代码又臭又长或许就是在这里……
我的做法是：把线按 (p) 排序，从小到大枚举。
每次把起点处的凸包能加线就加线，注意要加的 (qle) 这条线的 (p)。由于 (p) 从小到大枚举这个很简单。
然后在凸包上二分，把自己这条线加到终点的凸包的候选中。
不过由于我太菜，只想得到 set 维护凸包，所以写得很丑。
然后因为有二分，又要对相邻的线的交点再弄个 set……
无论如何时间复杂度 (O(mlog m))。
#include<bits/stdc++.h>
using namespace std;
const int maxn=400040;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
int x=0,f=0;char ch=getchar();
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
struct edge{
int u,v,p,q,id;
bool operator<(const edge &e)const{return q<e.q;}
}e[maxn];
bool cmp(edge e1,edge e2){return e1.p<e2.p;}
struct item{
int k,b;
bool operator<(const item &i)const{
if(k!=i.k) return k>i.k;
return b>i.b;
}
};
struct point{
double x;
int k,b;
bool operator<(const point &f)const{return x<f.x;}
};
int n,m,A,B,C,ans=2e9,f[maxn];
set<edge> in[maxn];
set<item> hull[maxn];
set<point> pt[maxn];
double interx(item i1,item i2){
return i1.k==i2.k?1e10:1.0*(i2.b-i1.b)/(i1.k-i2.k);
}
void remove(int id,set<item>::iterator it){
set<item>::iterator it1=it,it2=it;
it2++;
if(it1!=hull[id].begin()){
it1--;
pt[id].erase((point){interx(*it1,*it),it1->k,it1->b});
it1++;
}
if(it2!=hull[id].end()) pt[id].erase((point){interx(*it,*it2),it->k,it->b});
if(it1!=hull[id].begin() && it2!=hull[id].end()){
it1--;
pt[id].insert((point){interx(*it1,*it2),it1->k,it1->b});
}
hull[id].erase(it);
}
void insert(int id,item x){
set<item>::iterator it=hull[id].insert(x).first;
set<item>::iterator it1=it,it2=it;it2++;
if(it1!=hull[id].begin()){
it1--;
if(it->k==it1->k) hull[id].erase(it1);
else it1++;
}
if(it2!=hull[id].end()){
if(it->k==it2->k) return void(hull[id].erase(it));
}
it1=it2=it=hull[id].find(x);it2++;
if(it1!=hull[id].begin() && it2!=hull[id].end()){
it1--;
if(interx(x,*it1)>interx(x,*it2)) return void(hull[id].erase(x));
}
it=it1=it2=hull[id].find(x);it2++;
if(it1!=hull[id].begin() && it2!=hull[id].end()){
it1--;
pt[id].erase((point){interx(*it1,*it2),it1->k,it1->b});
it1++;
}
if(it1!=hull[id].begin()){
it1--;
pt[id].insert((point){interx(*it1,*it),it1->k,it1->b});
}
if(it2!=hull[id].end()) pt[id].insert((point){interx(*it,*it2),it->k,it->b});
it=it1=hull[id].find(x);
while(it1!=hull[id].begin()){
it1--;
if(it1==hull[id].begin()) break;
it2=it1;it2--;
if(interx(x,*it2)>interx(x,*it1)) remove(id,it1);
else break;
it=it1=hull[id].find(x);
}
it=it1=hull[id].find(x);it1++;
while(it1!=hull[id].end()){
it2=it1;it2++;
if(it2==hull[id].end()) break;
if(interx(x,*it2)<interx(x,*it1)) remove(id,it1);
else break;
it=it1=hull[id].find(x);it1++;
}
}
int main(){
n=read();m=read();A=read();B=read();C=read();
FOR(i,1,m){
int x=read(),y=read(),p=read(),q=read();
e[i]=(edge){x,y,p,q,i};
}
sort(e+1,e+m+1,cmp);
insert(1,(item){0,0});
FOR(i,1,m){
while(!in[e[i].u].empty() && in[e[i].u].begin()->q<=e[i].p){
int q=in[e[i].u].begin()->q,id=in[e[i].u].begin()->id;
insert(e[i].u,(item){-2*A*q,A*q*q-B*q+f[id]});
in[e[i].u].erase(in[e[i].u].begin());
}
if(hull[e[i].u].empty()) continue;
int p=e[i].p,k,b;
set<point>::iterator it=pt[e[i].u].lower_bound((point){e[i].p,-2e9,2e9});
if(it==pt[e[i].u].end()){
set<item>::iterator it=hull[e[i].u].end();it--;
k=it->k;b=it->b;
}
else k=it->k,b=it->b;
f[e[i].id]=A*p*p+B*p+C+k*p+b;
in[e[i].v].insert(e[i]);
if(e[i].v==n) ans=min(ans,f[e[i].id]+e[i].q);
}
printf("%d
",ans);
}