题目大意：
给定 n n n个点，从 1 1 1走到 n n n，其中有 m m m第一条路径 x i x_i xi到 y i y_i yi，时间从 p i p_i pi到 q i q_i qi，每次等t的时间都会增加 A t 2 B t C At^2 Bt C At2+ Bt+ C 的花费，最后花费加上到达时间即为最终花费，使
解题思路：
可能可以实现但太麻烦了的想法：
- 设 d p [ i ] [ j ] dp[i][j] dp[i][j]为到达第i个点j时刻的最小花费，然后 d p dp dp方程自然而然可以通过相连的边来转移，但是因为这样子，可以用，而空间则可以发现每个点仅仅只有那些入边的到达时间，所以可以对每个点分别 n e w new new一个大小为入边个数的空间来转移，空间大小为 O ( n + m ) O(n+m) O(n+m)
容易实现的想法：
- 设 d p [ i ] dp[i] dp[i]为走到 i i i路径的最小总花费，那么 d p [ i ] = m i n ( d p [ i ] , d p [ j ] + A ∗ ( p i − q j ) 2 + B ∗ ( p i − q j ) + C ) dp[i]=min(dp[i],dp[j]+A*(p_i-q_j)^2+B*(p_i-q_j)+C) dp[i]=min(dp[i],dp[j]+A∗(pi−qj)2+B∗(pi−qj)+C)
- 可将其转换为： d p [ j ] + A q j 2 − B q j = 2 A p i q j + d p [ i ] − A p i 2 − B p i 2 − C dp[j]+Aq_j^2-Bq_j=2Ap_iq_j+dp[i]-Ap_i^2-Bp_i^2-C dp[j]+Aqj2−Bqj=2Apiqj+dp[i]−Api2−Bpi2−C
- x = q j , y = d p [ j ] + A q j 2 − B q j , k = 2 A p i x=q_j,y=dp[j]+Aq_j^2-Bq_j,k=2Ap_i x=qj,y=dp[j]+Aqj2−Bqj,k=2Api，求截距最小即是的内容
- 把m条路径按照 p p p从小到大处理， k k k单调不减，即可进行斜率优化(剩下这段话来自Mentos_Cola)
- 但是还有两个限制，一个是 y j = x i y_j=x_i yj=xi，另一个是 q j ≤ p i q_j\le p_i qj≤pi
- 第一个好办，我们开 n n n个单调队列，i进队时就丢进第 y i y_i yi个单调队列里，求 d p [ i ] dp[i] dp[i]时就从第 x i x_i xi个单调队列里调就完了。
- 第二个则需要我们算出 d p [ i ] dp[i] dp[i]后不将它马上插到对应的单调队列里，而是按照 q q q把它丢到桶里。对每个 d d d算所有 p i = d p_i=d pi=d的 d p [ i ] dp[i] dp[i]之前，就把所有 q j = d q_j=d qj=d的 j j j插入对应单调队列
- 可行的原因是因为，在计算 d p [ i ] dp[i] dp[i]时，桶里面所有 q j ≤ p i q_j\le p_i qj≤pi都会进入单调队列中，而所有 q j ≤ p i q_j \le p_i qj≤pi的j必然 p j < p i p_j < p_i pj<pi，他们一定之前就会进入桶中，所以就不会有任何遗漏
AC代码：
#include <bits/stdc++.h>
#define ft first
#define sd second
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 1e5 + 10;
const int maxm = 1e6 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;
int n, m;
ll ans = -1;
ll a, b, c, x[maxm], y[maxm], p[maxm], q[maxm], dp[maxm];
int h[maxn], t[maxn];
//因为不可能开maxn*maxm的队列，所以开vector，这样动态开出的空间为maxn+maxm
vector <int> ton[maxn], g[maxn], dq[maxn];
pll operator - (pll p1, pll p2) {
return {
p1.ft - p2.ft, p1.sd - p2.sd};}
ll operator ^ (pll p1, pll p2) {
return p1.ft * p2.sd - p2.ft * p1.sd;}
ll sqr(ll x) {
return x * x;}
bool cal(int i, int j, int k) {
pll pi = {
q[i], dp[i] + a * sqr(q[i]) - b * q[i]}, pj = {
q[j], dp[j] + a * sqr(q[j]) - b * q[j]}, pk = {
q[k], dp[k] + a * sqr(q[k]) - b * q[k]};
return ((pj - pi) ^ (pk - pi)) <= 0; //存储的是一个下凸包，这里要等于不然会有错误
}
bool cmp(int i, int j, int k) {
return ((dp[i] + a * sqr(q[i]) - b * q[i]) - (dp[j] + a * sqr(q[j]) - b * q[j])) < k * (q[i] - q[j]);
}
int main() {
// freopen("data.txt", "r", stdin);
ll mx = 0;
cin >> n >> m >> a >> b >> c;
for (int i = 1; i <= n; i++) h[i] = 0, t[i] = -1;
for (int i = 1; i <= m; i++) {
cin >> x[i] >> y[i] >> p[i] >> q[i];
mx = max(mx, q[i]); //最大时间
g[p[i]].push_back(i);
}
for (int ti = 0; ti <= mx; ti++) {
//时间从小到大枚举，即相当于枚举从小到大枚举pi了
for (auto np : ton[ti]) {
//先将该时间内的dp值存进相应队列
int f = y[np];
while (h[f] < t[f] && cal(dq[f][t[f] - 1], dq[f][t[f]], np))
t[f]--, dq[f].pop_back();
dq[f].push_back(np);
t[f]++;
}
for (auto np : g[ti]) {
int f = x[np], k = 2 * a * p[np];
while (h[f] < t[f] && cmp(dq[f][h[f] + 1], dq[f][h[f]], k))
h[f]++;
if (h[f] > t[f] && x[np] != 1) continue; //因为起点为1的话，队列里必然是空的，因为根据转移方程不会有这样的边，所以就从0转移
int g;
if (h[f] > t[f] && x[np] == 1) g = 0;
else g = dq[f][h[f]];
dp[np] = dp[g] + a * sqr(p[np] - q[g]) + b * (p[np] - q[g]) + c;
if (y[np] == n) {
//统计答案
if (ans == -1) ans = dp[np] + q[np];
else ans = min(ans, dp[np] + q[np]);
}
ton[q[np]].push_back(np);
}
}
// for (int i = 1; i <= m; i++)
// cout << dp[i] << " \n"[i == m];
cout << ans << endl;
}